2007-04-26

Magia w tcp/ip linuxa. Bug czy ficzer?

Z tcp/ip dzieje się coś dziwnego, po odpaleniu skryptu, pierwsze dwa połączenia są poprawnie nawiązane. Natomiast system nie widzi trzeciego połączenia. Syn-ack po sieci śmiga, a jądro z jakichś powodów go nie zauważa.
Netstat pisze:

tcp        0      0 127.0.0.1:60885         127.0.0.1:8081          ESTABLISHED
tcp 0 0 127.0.0.1:8081 127.0.0.1:60885 ESTABLISHED

tcp 0 0 127.0.0.1:60886 127.0.0.1:8081 ESTABLISHED
tcp 0 0 127.0.0.1:8081 127.0.0.1:60886 ESTABLISHED

tcp 0 0 127.0.0.1:60887 127.0.0.1:8081 ESTABLISHED
tcp 0 0 127.0.0.1:8081 127.0.0.1:60887 SYN_RECV


Taka magia, że jest SYN_RECV w jedną stronę a ESTABLISHED w drugą. Kiedyś posiedzę nad tym dłużej i wyjaśnię :)

Oto jak zreprodukować to dziwne zachowanie:
a) Odpal skrypt.
b) Na innej konsoli uruchom
tcpdump -np -i any port 8081

Jak już powiedziałem, z trzecim połączeniem dzieje się magia.

A może ktoś zna racjonalne wyjaśnienie? Jakiś ficzer protokołu tcp/ip czy bug kernela?

POPRAWKA:
Wyjaśniło się. To jest ficzer jajka, wymyślony przez Van Jacobsena. Chodzi o to, żeby w przypadku gdy kolejka się przepełni nie odrzucać połączenia. Host będzie się dobijał dłużej, i możliwe że za którymś razem będzie miejsce dla niego w kolejce.

Ja bym to zaimplementował po prostu dropując pierwszy pakiet SYN, lecz widać z jakichś powodów dropują dopiero ACK.

Aby wyłączyć takie zachowanie można użyć:
 echo 1 > /proc/sys/net/ipv4/tcp_abort_on_overflow


2007-04-19

Web 2.0

Czym właściwie jest web 2.0? Spotkałem się z kilkoma definicjami.

  • Web 2.0 to serwisy społecznościowe, gdzie każdy użytkownik może wpływać na prezentowaną treść. Taka definicja jest chyba najbardziej popularna.
  • Podejście techniczne, gdzie aby utrzymać serwery portali społecznościowych potrzebne są zupełnie nowe rozwiązania dotyczące skalowania serwerowni. Web 2.0 w tym kontekście to nie ludzie i treść, lecz waty, procesory i nacisk na skalowalność.
  • Oddzielenie formy od treści i dowolne łączenie treści. Głównym przykładem może być serwowanie danych jako xml + xslt.


Nmap nse-pcap, próba #2

Właśnie skończyłem testować patch do nmapa, o roboczej nazwie nse-pcap.

Zamiast opisywać jego działanie powiem tylko, że jest po prostu zajebisty.

Wkrótce postaram się opisać jego możliwości.



2007-04-18

Python wrappers for memcache

Jeśli szukasz modułu do pythona, którym połączysz się do memcached, to najprostszym będzie python-memcached. Jest on prosty, stabilny, i po prostu działa.

Problem zaczyna się później w memcache.py:_Host.readline()


def readline(self):
buffers = ''
recv = self.socket.recv
while 1:
data = recv(1)
[...]

Tak, tak. python-memcache czyta z socketa po jednym bajcie. To był główny powód zainteresowania wrapperem pythona do libmemcache, czyli cmemcache.

Niestety cmemcache jest trochę niedorobiony. Jest to wina libmemcache, który w niektórych przypadkach potrafi brutalnie wywołać exit(). A nie jest to miłe, gdy proces pythona zdycha od jakiegoś głupiego błędu na socketach. Napisałem patch do libmemcache.
Drugim problemem jest to, że api cmemcache jest troszeczkę inne niż python-memcached. Na przykład "set" zwraca -1 lub 0, zamiast 0 lub 1. Naprawiliśmy to banalnym patchem do cmemcache.


PS. W nowym python-memcached już nie robią recv(1), oto odpowiedni fragment kodu:

def readline(self):
buf = self.buffer
recv = self.socket.recv
while True:
index = buf.find('\r\n')
if index >= 0:
break
data = recv(4096)


2007-04-11

Keep It Simple, Stupid

Cytat z bloga toomuchcode:

For anyone that might be struggling with this right now, some humble advice:

  • Follow Alan Kay's axiom: "Simple things should be simple, complex things should be possible." -- If something complicated must be in the system, it still should not affect the simple things.
  • View the project as a constant battle against complexity -- A single complex module may seem unimportant, but it quickly compounds.
  • Understand a project end-to-end -- the project should be easily broken down into problems that are known to be solvable. (Avoid Southpark's 1. Collect Underpants. 2. ??? 3. Profit!!!).
  • A strong-willed engineer or executive can will a group down the wrong path -- it's an engineer's duty to object and prevent spiraling complexity
  • The clever hack should be a last resort -- a hack that is hard to come up with is much harder to debug or support
All of this boils down to Keep It Simple, Stupid. It turns out keeping things simple is pretty hard.


2007-04-10

Praktyki w Mountain View? Nie tym razem.

Złożyłem papiery na praktyki w Google. A co mi tam, przecież każdy chce tam pracować. Po jakimś czasie (ok 1,5 miesiąca) mejlem odezwała się grzeczna pani, i ustaliliśmy termin na dwie 45-cio minutowe rozmowy.

Obie rozmowy odbyły się z regularnymi pracownikami Google - w pierwszej rozmawiałem z gościem z ładnym angielskim akcentem, a podczas drugiej z facetem, którego ledwo mogłem zrozumieć, bo strasznie terkotał po amerykańsku.

Rozmowy przebiegały mniej więcej podobnie: najpierw gadka na rozgrzewkę, potem pytanko z baz danych, pytanie lub dwa z algorytmiki i na koniec zadanie do którego trzeba napisać (podyktować) krótki program.

Nic nie podpisywałem, więc raczej mogę swobodnie mówić o pytaniach, które mi zadano. Oto one, może komuś pomogą:

Pytania z baz danych:

  1. left inner join, right inner join , outer join itp.
  2. pytanko na użycie Count i Group by
    (dwie tabele, pierwsza: id_pracownika, wynagrodzenie, id_działu; druga: id_działu,id_managera, podać liczbę pracowników na dział, i średnie wynagrodzenie pracowników dla podległych managerowi)

Proste algorytmicze:
  1. Tablica jednowymiarowa, rozmiar N. Trzeba utworzyć na wyjściu tablicę P w której w każdym polu P[i] będzie iloczyn wszystkich elementów tablicy N za wyjątkiem N[i]. Czyli dla N=[2,3,4] wynikiem będzie P=[3*4, 2*4, 2*3]. Podać złożoność i koszt pamięciowy proponowanych rozwiązań. Ja wpadłem od razu na koszt O(n), ale doprecyzowano zadanie, że nie mamy operacji dzielenia :)
  2. Jak znaleźć medianę i jakim kosztem?
  3. Jak scalić i jakim kosztem, dwie tabele A=(aid, akey) i B=(bid, bkey) zakładając że obie są:
    1. posortowane
    2. tylko b jest posortowana
    3. obie są nieposortowane

Pytanka algorytmiczne, trzeba napisać prostą funkcję która je rozwiązuje:
  1. Pusta tablica NxN, zaczynamy chodzić po niej od lewego górnego rogu, trzeba dojść do prawego dolnego. Mamy możliwe tylko ruch w prawo i w dół. Napisać program, który wypisze wszystkie możliwe ścieżki dojścia od początku do celu. Oczywiście chodzi o to, żeby pokazać czy się umie zastosować rekurencję.
  2. Mamy dostępne trzy literki A, trzy literki B, trzy literki C.
    1. napisać funckcję która wypisze wszystkie ciągi trzy literowe możliwe do utworzenia z tych liter
    2. jak wyżej, ale ciągi pięcio znakowe
Jeśli komuś te pytania w czymś pomogą to proszę postawić mi piwo.

Podczas rozmowy bardzo miło mi się rozmawiało, ale niestety nie przyjeli mnie.

Ich strata, może czas zacząć karierę, w Polsce?


2007-04-08

Zagadka o piratach i łupie

Dziesięciu piratów zdobyło skarb złożony ze stu sztuk złota। Chcą podzielić się łupem. Są, na swój własny i szczególny sposób, piratami demokratycznymi - mają zwyczaj dzielenia łupów w następujący sposób. Najgwałtowniejszy pirat proponuje metodę podziału i wszyscy głosują; każdy ma jeden głos, wnioskodawca też. Jeśli 50% lub więcej głosów jest za, propozycja zostaje zatwierdzona i wciela się ją w życie. W przeciwnym przypadku wnioskodawca zostaje wyrzucony za burtę i cała procedura zostaje powtórzona przez najgwałtowniejszego z pozostałych piratów.



Wszyscy piraci lubią wyrzucać ludzi za burtę, ale - jeśli mają wybór - wolą twardą gotówkę. Sami nie lubią być wyrzucani za burtę. Wszyscy piradci działają racjonalnie, wiedzą, że inni piraci też działają racjonalnie, wiedzą, że oni wiedzą, że ... i tak dalej.



Jaka propozycja podziału łupów maksymalizuje dolę najgwałtowniejszego pirata?



Idea silniejsza niż Microsoft

Dziś przeczytałem dwa ważne artykuły, polecam do poduszki:



2007-04-07

Zagadka "najtrudniejsza ze wszystkich"

Poniższa zagadka, znana jako "Historia Smitha, Johnesa i Robinsona" to już klasyka tego typu łamigłówek.

Panowie Smith, Robinson i Jones stanowią załogę pociągu. Jeden jest palaczem, drugi hamulcowym, trzeci maszynistą; kolejność tych funkcji jest przypadkowa. Pociągiem jadą również trzej biznesmeni o tych samych nazwiskach.
1. Pan Robinson mieszka w Detroit.
2. Hamulcowy mieszka dokładnie w połowie drogi między Chicago i Detroit.
3. Pan Jones zarabia dokładnie 20 tysięcy dolarów rocznie.
4. Najbliższy sąsiad hamulcowego, pasażer, zarabia 3 razy tyle co on.
5. Smith zawsze wygrywa z palaczem w bilard.
6. Pasażer o takim samym nazwisku jak hamulcowy mieszka w Chicago.

Jak nazywa się maszynista?



Zagadka "Einsteina"

Tak na rozruszanie głowy, oto pewna zagadka:

5 ludzi zamieszkuje 5 domów w 5 różnych kolorach. Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują zwierzęta 5 różnych gatunków.

- Anglik mieszka w czerwonym domu
- Duńczyk pija herbatkę
- Norweg zamieszkuje pierwszy dom
- Palacz Rothmansów mieszka obok hodowcy kotów
- Mieszkaniec żółtego domu pali Dunhille
- Niemiec pali Marlboro
- Mieszkaniec środkowego domu pija mleko
- Palacz Rothmansów ma sąsiada, który pija wodę
- Palacz Pall Malli hoduje ptaki
- Szwed hoduje psy
- Norweg mieszka obok niebieskiego domu
- Hodowca koni mieszka obok żółtego domu
- Palacz Philip Morris pija piwo
- Zielony dom znajduje się po lewej stronie domu białego
- W zielonym domu pija się kawę

Kto hoduje rybki?

Podobno zadanie to zostało wymyślone przez Einsteina.
Według niego 98% ludzkiej populacji nie jest w stanie go rozwiązać!



2007-04-06

Wyraz tygodnia

Miło mi, po raz pierwszy, ogłosić wyraz tygodnia. Tym razem zwycięzcą jest tajemnicza "INWALIDACJA", wraz z odpowiednikiem: "INWAGINACJA".



2007-04-05

Niskopoziomowy debugging w linuxie, czyli gdzie się podziały DR0-DR7?

Przypomniałem sobie, że przecierz i386 ma rejestry służące do debuggowania! A świat o nich zapomniał tak dawno.
Nie bardzo jeszcze wiem do czego może się przydać ich używanie, ale to nie jest ważne :)

No to do roboty!

Wiadomo że gdb potrafi używać sprzętowego debugowania, komunikaty w stylu poniższego już nie raz śniły mi się:
(gdb) awatch *(0x8049534)
Hardware access (read/write) watchpoint 1: *134518068


Pytanie tylko, jak to działa. To co wiem, to że na pewno ptrace
jest podstawą działania gdb. Choć z drugiej strony w dokumentacji
ptrace nie ma żadnej wzmianki na temat ustawiania rejestrów DR.

Skrobnijmy pierwszy programik:
#include <stdio.h>
int main(){
unsigned long db_regs;
asm volatile ("mov %%dr0, %0" : "=r"(db_regs));
printf("%08lx\n", db_regs);
return(0);
}


majek:~/mutex$ gcc -Wall a.c
majek:~/mutex$ ./a.out
Segmentation fault

No tak, to było do przewidzenia, przecierz w dokumentacji intela pisze jednoznacznie: "The debug registers are privileged resources; the MOV instructions that access them can only be executed at privilege level zero." Hmm, ale gdb potrafi ustawiać je bez roota.

Weźmy nowy, równie prosty program, ale tym razem interesuje nas, jak działa gdb:
#include <stdio.h>
int i;
int main(){
for(i=0; i<4; i++);
return(0);
}


majek:~/mutex$ gcc -Wall b.c
majek:~/mutex$ strace gdb ./a.out 2>log
(gdb) maint show-debug-regs on
(gdb) awatch i
Hardware access (read/write) watchpoint 1: i
(gdb) run
Starting program: a.out
[....]
watchpoint_hit (addr=8049534, len=-1, type=data-write):
CONTROL (DR7): 000f0101 STATUS (DR6): ffff4ff1
DR0: addr=0x08049534, ref.count=1 DR1: addr=0x0000000, ref.count=0
DR2: addr=0x00000000, ref.count=0 DR3: addr=0x0000000, ref.count=0
remove_watchpoint (addr=8049534, len=4, type=data-read/write):
CONTROL (DR7): 000f0100 STATUS (DR6): ffff4ff1
DR0: addr=0x00000000, ref.count=0 DR1: addr=0x0000000, ref.count=0
DR2: addr=0x00000000, ref.count=0 DR3: addr=0x0000000, ref.count=0
Hardware access (read/write) watchpoint 1: i

Więc gdb jednak jakoś odczytał zawartość DR0-DR7, a nawet je ustawił.
Zajrzyjmy do loga strace:
majek:~/mutex$ cat log <palka> grep ptrace <palka> grep USER
[....]
ptrace(PTRACE_PEEKUSER, 28498, offsetof(struct user, u_debugreg) + 24, [0xffff4ff1]) = 0
ptrace(PTRACE_POKEUSER, 28498, offsetof(struct user, u_debugreg) + 28, 0xf0100) = 0
ptrace(PTRACE_POKEUSER, 28498, offsetof(struct user, u_debugreg), 0) = 0
[....]

No to mamy już całą magię. Jeszcze rzut okiem na <sys/user.h> I mamy już pełną jasność, ptrace z pierwszej linijki odczytuje DR7, a kolejne dwie linijki zapisują dane do DR7 i DR0.

No to programik testowy, tym razem dłuższy więc w zamieszczam tylko w osobnym pliku.
majek:~/mutex$ gcc -Wall c.c && ./a.out
#28848 child started
#28847 parent started
before change: DR0=0x00000000 DR7=0x00000000
after change: DR0=0x08049a3c DR7=0x00050101
#28847 parent stopped
#28848 got SIGTRAP
#28848 child stopped

Hurray! Udało się. Zmieniając zmienną wywołujemy SIGTRAP dla naszego procesu, i SIGCHLD dla procesu który nas śledzi.

Dla czytelnika zostawiam pytanie do czego użyć prezentowanej techniki.

Myślę, że niektórzy mogą się domyślać co kombinuję, ale zostawmy to na kolejny wpis.



Specjalizacja jest dla szarańczy

Cytat na dziś:

"For me, staying psyched about programming definitely requires lots of extrinsic inspiration; I'm a better programmer when I have time to ride my bike, and run, and play with my daughter, and laugh with my wife."

"A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects."

-Robert A. Heinlein