Checking Whether IP is Within a Subnet

Recently I had to solve a simple but very practical coding puzzle. The task was to check whether an IPv4 address (given in traditional dot notation) - is within specified network, described as a CIDR block.
You may notice that this is almost as ubiquitous as a programming problem can get. Implementations of its simplified version are executed literally millions (if not billions) of times per second, for every IP packet at every junction of this immensely vast Internet. Yet, when it comes to doing such thing in Python, one is actually left without much help from the standard library and must simply Do It Yourself.

It's not particularly hard, of course. But before jumping to a solution, let's look how we expect our function to behave:

Pretty obvious, isn't it? Now, if you recall how packet routing works under the hood, you might remember that there are some bitwise operations involved. They are necessary to determine whether specific IP address can be found within given network. However low-level this may sound, there is really no escape from doing it this way. Yes, even in Python :P

It goes deeper, though. Most of the interface of Python's socket module is actually carbon-copied from POSIX socket.h and related headers, down to exact names of particular functions. As a result, solving our task in C isn't very different from doing it in Python. I'd even argue that the C version is clearer and easier to follow. This is how it could look like:

A similar thing done in Python obviously requires less scaffolding, but it also introduces its own intricacies via struct module (for unpacking bytes). All in all, it seems like there is not much to be gained here from Python's high level of abstraction.

And that's perfectly OK: no language is a silver bullet. Sometimes we need to do things the quirky way.

Odkrycie archeologiczne

Sprzed prawie czterech lat pochodzi pewien niewielki (~2KLOC) projekt uczelniany, na który natknąłem się kilka dni temu w swoich przepastnych archiwach i postanowiłem upublicznić. Jest to implementacja prostego (acz zupełnie funkcjonalnego) serwera FTP, napisana w czystym C pod systemy POSIX-owe. Nie spodziewam się bynajmniej, aby mogła znaleźć rzeczywiste zastosowanie jako kawałek oprogramowania. Jest ona jednak całkiem interesująca jako kawałek kodu.

Wielu znany jest zapewne "syndrom następnego pół roku". Polega on na tym, że gdy po pół roku (plus/minus kilka miesięcy) spoglądamy na stworzony przez siebie kod, widzimy go tak, jakby napisał go ktoś zupełnie inny. Zazwyczaj wręcz trudno nam się w nim połapać i szybko dochodzimy do wniosku, że teraz napisalibyśmy go zdecydowanie lepiej. Nasz twór traktujemy więc jako bezwarto... ekhm... legacy code (;]), i uważamy to za naturalną kolej rzeczy.

Jednak moje niedawne znalezisku okazało się pod tym względem sporym zaskoczeniem. Nietypowe jest bowiem to, jak przetrwało ono próbę czasu. Na jego podstawie muszę dojść do lekko szokującego wniosku, iż Xion₂₀₀₇ potrafił - o zgrozo - pisać dobry kod. Robił to wprawdzie ostrożnie i raczej niepewnie (czego dowodem była przesadna ilość komentarzy), ale koniec końców udawało mu się to całkiem nieźle. Wysyłając mu wiadomość z przyszłości, mógłbym wprawdzie wspomnieć o zaletach podziału kodu na pliki krótsze niż 800-linijkowe, lecz poza tym do niewielu rzeczy mógłbym się przyczepić. To zupełnie akceptowalny, czytelny i przejrzysty kod w C...

Madness!

Biedny, biedny JavaScript

Przyznam, iż jestem trochę zaskoczony. Okazuje się bowiem, że niekiedy zupełnie nie udaje mi się skomunikować tego, co mam w rzeczywistości na myśli. A wydawać by się mogło, że przynajmniej te 500+ notek na blogu powinno dość skutecznie nauczyć mnie, jak klarownie formułować swoje stwierdzenia i opinie. Teoretycznie niby też wiem, że zrozumienie jest często podwójną iluzją, więc z dwóch wyjaśnień należy zawsze wybierać te łatwiejsze i bardziej bezpośrednie - także wtedy, gdy trzeba je dopiero znaleźć. To wszystko wydaje się oczywiste, dopóki - jak się przekonałem - nie okaże się trudne w praktycznym stosowaniu.

O co mi w tym miejscu chodzi? Ano o to, iż niesłusznie zostałem uznany przez kilka osób za - nieco wyolbrzymiając - hejtera JavaScriptu. Tak została przez niektórych odebrana moja niedawna publikacja slajdów z prezentacji pod tytułem The Beauty and the JavaScript; tytułem, który rzeczywiście może dawać co nieco do myślenia ;) I chociaż mógłbym uznać, że wchodzi tu w grę głównie kwestia oceny wykładu po samych slajdach, to jakoś wydaje mi się, że wypadałoby tu dokonać małego sprostowania. Dzięki temu mógłbym też napisać, jak to właściwie jest z tą moją opinią o JavaScripcie, który przecież już od dłuższego czasu jest sam w sobie bardzo nośnym tematem.

Spieszę więc z wyjaśnieniem, że w kwestii JavaScriptu mam raczej osobliwą opinię. Otóż przede wszystkim jest mi go... żal.

printf(“R.I.P.”);

Branża IT oraz nauka zwana informatyką liczą sobie już ładnych kilkadziesiąt i wygląda na to, że dziedzina ta zaczyna w pewnym sensie "dorastać". W dość nieprzyjemnym sensie, muszę dodać. Jej znani pionierzy zaczynają bowiem nas opuszczać, czego dobitym dowodem jest zeszły miesiąc, gdy kilku z nich pożegnaliśmy w ciągu stosunkowo krótkiego czasu.
Ponieważ dzisiejszy dzień jest dobrą okazją do takich wspomnień, pozwolę sobie zwrócić uwagę na jednego z nich. Tego, który bez wątpienia miał największy wpływ na to, w jaki sposób programujemy komputery i jak obecnie wygląda przemysł software'owy.

Mam tu na myśli oczywiście Dennisa Ritchie.

Wpływ Ritchiego na kształt informatyki jest trudny do przeceniania, bowiem miał on ogromny udział w początkach rozwoju dwóch jej ważnych aspektów: języków programowania i systemów operacyjnych. Jego zasługi w pierwszej z tych dziedzin wyrażają się głównie w stworzeniu języka C - prawdopodobnie najszerzej wykorzystywanego języka programowania w historii IT. Nawet jeśli sami nigdy w C nie programowaliśmy, to istnieje bardzo duża szansa, że nasz ulubiony język programowania ma z C wiele wspólnego: począwszy od bezpośredniej historii (C++, Objective-C), poprzez składnię (C#, Java, JavaScript, D, Scala, Go, itp.) aż po kluczowe narzędzia w rodzaju interpreterów napisanych w C (Python, Ruby, Perl, PHP). W rzeczywistości trudno jest wskazać język, który nie miałby czegokolwiek wspólnego z C - z ważniejszych należą do nich chyba tylko wczesne warianty Lispa (którego twórca, notabene, również zmarł w zeszłym miesiącu...). Niełatwo jest więc przesadzić, mówiąc o decydującym wpływie Ritchie'ego na kształt narzędzi używanych obecnie przez programistów na całym świecie.

Podobnie jest zresztą z oprogramowaniem w ogóle. System UNIX - którego Ritchie był jednym z kluczowych twórców - w niezliczonych odmianach i pochodnych działa na sporej części istniejących komputerów i wyrobów komputeropodobnych. Dotyczy to zarówno superkomputerów, wielkich serwerowni (żeby nie użyć słowa na 'ch' ;]) oraz małych serwerów, ale też domowych PC-tów i laptopów, a nawet urządzeń mobilnych: telefonów i tabletów. Większość (albo przynajmniej duża część) z nich operuje pod kontrolą systemów wywodzących się z UNIX-a i używa przynajmniej części związanego z nim stosu oprogramowania, którego prawdopodobnie najważniejszym komponentem jest... dokładnie tak - kompilator C.

Nie ma oczywiście żadnej pojedynczej osoby, której moglibyśmy zawdzięczać obecną postać technologii obliczeniowych i informacyjnych. Jednak Dennis Ritchie jest bez wątpienia człowiekiem, bez którego wyglądałaby ona dzisiaj zupełnie inaczej. Dlatego też warto o nim pamiętać - nawet jeśli wskaźniki z C czy uniksowy terminal są dla nas strasznymi rzeczami, z którymi nie chcemy mieć nic wspólnego :)

C++11 est arrivé!

O ile tylko ktoś nie spędził zeszłego tygodnia na Antarktydzie, w amazońskiej dżungli czy w innym podobnie odciętym od cywilizacji miejscu, z pewnością słyszał najważniejszą nowinę ostatnich lat. A już na pewno wspomnianego tygodnia - bo przecież jak tu ją nawet porównywać z takimi błahostkami jak choćby zakup Motoroli przez Google. Przecież mówimy tutaj o pomyślnym końcu procesu rozpoczętego w czasach, gdy Google nawet nie istniał! To musi robić wrażenie... I nawet jeśli owym wrażeniem jest głównie: "No wreszcie; co tak długo?!", to przecież w niczym nie umniejsza to rangi wydarzenia.

Tak, mamy w końcu nowy standard C++! I to w sumie mogłoby wystarczyć za całą notkę, bo chyba wszystko, co można by powiedzieć na temat kolejnej wersji jednego z najważniejszych języków programowania, zostało już pewnie dawno powiedziane w dziesiątkach serwisów informacyjnych, tysiącach blogów i milionach tweetów. Znaczącą ich część zajmują omówienia nowych możliwości języka, dostępnych zresztą od jakiegoś czasu (acz w niepełnej formie) w kilku wiodących kompilatorach. Możliwości tych jest całkiem sporo i dlatego nie mam zamiaru nawet wyliczać ich wszystkich. Zdecydowałem, że w zamian przyjrzę się bliżej tylko trzem z nich - tym, które uważam za najbardziej znaczące i warte uwagi.

Etykiety też mają adresy

Natrafiłem niedawno na kapitalną ciekawostkę, sponsorowaną przez literkę C - język C, rzecz jasna. A jeśli już o C mowa, to jednym z pierwszym skojarzeń są oczywiście wskaźniki; prawdopodobnie nie jest ono zresztą specjalnie pozytywne ;) Wśród nich mamy wskaźniki na funkcje, które znane są z kilku nieocenionych zastosowań (weźmy na przykład funkcję qsort), ale przede wszystkim z pokrętnej i niezbyt oczywistej składni.

Zalecam jednak przypomnienie jej sobie, bo dzisiaj będzie właśnie o wskaźnikach na funkcje, tyle że pokazujących na... etykiety. Tak, te właśnie etykiety (labels), które normalnie są celem instrukcji goto - złej, niezalecanej, i tak dalej. Okazuje się bowiem, że etykiety też mają swoje adresy, które w dodatku można pobrać i wykorzystać jako wskaźniki:

Wymagany jest do tego podwójny znak ampersandu (&), co można traktować jako osobny operator lub rodzaj specjalnej składni... W każdym razie jest on konieczny, aby kompilator wiedział, że następująca dalej nazwa jest etykietą. Mają one bowiem swoją własną przestrzeń nazw, co oznacza, że możliwe jest występowanie np. zmiennej start i etykiety start w tym samym zasięgu.
Przykładowym wynikiem działania programu jest poniższa linijka:

first = 0x4004f8, second = 0x4004f8, last = 0x400519

Pierwsze dwa adresy są sobie równe i nie powinno to właściwie być zaskakujące. Jak można się bowiem łatwo domyślić, adresy etykiet to w istocie adresy instrukcji, które są nimi opatrzone. Dla osób programujących w asemblerze powinno być to dziwnie znajome :) W powyższym przykładzie zarówno first, jak i second mają adresy odpowiadające położeniu w pamięci kodu wywołania funkcji printf.

Wróćmy jednak do wspomnianych wcześniej wskaźników na funkcje. Mając bowiem pobrany adres etykiety, możemy go przypisać do takiego właśnie wskaźnika. Dzięki temu możemy etykiety możemy "wywoływać", i to nawet z innych funkcji!
Jak to jednak w ogóle działa? Ilustruje to poniższy przykład, w którym funkcja wywołuje w ten sposób sama siebie:

Po pobieżnym przyjrzeniu się widać, że jest to zwykłe liniowe przeszukiwanie tablicy, w dodatku w sposób który wygląda na rekurencyjny... Jest to jednak specjalny rodzaj tzw. rekurencji ogonowej (tail recursion). Występuje ona wówczas, gdy wywołanie rekurencyjne jest ostatnią instrukcją funkcji. Taki przypadek może być wówczas zoptymalizowany przez co sprytniejsze kompilatory poprzez wyeliminowanie konieczności ponownego odkładania argumentów na stos. Kolejny poziom rekursji wykorzystuje po prostu te same argumenty - jest to możliwe, o ile nie ma konieczności rekurencyjnych powrotów i składania kolejnych wyników.
W powyższym przykładzie rekursja ogonowa występuje jednak niezależnie od jakichkolwiek optymalizacji, gdyż jest ona zawarta w "wywołaniu" etykiety top. Chociaż pozornie wygląda to jak wywołanie funkcji, nie powoduje utworzenia dodatkowej ramki stosu ani ponownego odłożenia na nim argumentów. Docelowa "funkcja" operuje na istniejącym stosie. W istocie więc mamy tu do czynienia z pewną wersją instrukcji goto, czyli zwykłego skoku.

Ciekawiej zaczyna się robić wtedy, gdy spróbujemy "wywołać" etykietę z innej funkcji, co - jak wspomniałem - jest zupełnie możliwe. Możliwe jest wówczas gładkie przekazanie jej wszystkich parametrów oraz zmiennych lokalnych, co automatycznie podpada pod kategorię Rzeczy Podejrzanych i Potencjalnie Niebezpiecznych :) Niemniej jednak jest to możliwe:

Powyższy program przekazuje swoje argumenty do funkcji process (która je wypisuje) mimo iż zupełnie tego nie widać w jej wywołaniu. Zresztą normalne wywołanie tej funkcji jedynie zwraca adres jej etykiety, pod który później skaczemy z maina bez dokładania nowej ramki do stosu.

W tym kodzie jest też kilka innych smaczków (jak chociażby rola zmiennej foo), których odkrycie pozostawiam jednak co bardziej dociekliwym czytelnikom :) Zaznaczę tylko, że cała ta (chyba) niezbyt praktyczna zabawa z pobieraniem adresów etykiet jest w gruncie rzeczy rozszerzeniem GCC i nie jestem pewien, czy będzie działać w jakimkolwiek innym kompilatorze.

Recykling nazw w kodzie

W dziedzinie optymalizacji kodu pojawia się często pojęcie aliasowania. Z grubsza polega ono na tym, że jakaś komórka pamięci (lub bardziej ogólnie: zmienna) może być dostępna pod więcej niż jedną "nazwą" czyli np. wskaźnikiem lub referencją. Taka sytuacja sprawia, że kompilator ma mniejsze pole manewru w zakresie optymalizacji dostępu do niej. Typową konsekwencją jest konieczność ponownego odczytywania wartości tej komórki zamiast posłużenia się cache'owanym rezultatem zapisanym w jednym z rejestrów procesora.
Aliasing w większym lub mniejszym stopniu dotyczy właściwie wszystkich języków kompilowanych. Jest on jednak brany pod uwagę głównie tam, gdzie jego wpływ na wydajność jest największy, tj. w kodzie kompilowanym bezpośrednio do instrukcji maszynowych konkretnego sprzętu. Kod w C i C++ to najważniejszy przykład tego rodzaju.

Niejako na przeciwnym biegunie - zwłaszcza pod względem liczby warstw abstrakcji pod spodem - sytuują się języki interpretowane z dynamicznym typowaniem. Javascript i Python są tutaj typowymi reprezentantami. W nich problem "aliasowania" przybiera według mnie formę dokładnie odwrotną i nie dotyczy już kwestii wydajnościowych - z których wspomniane języki przecież nie słyną :) Przeciwnie: ów symetryczny problem jest związany z ich wyróżniającą zaletą: prostotą i czytelnością kodu.
O jaki więc rodzaj aliasowania chodzi? Ano taki, który polega na używaniu jednej nazwy do wielu różnych wartości. Przy czym 'nazwę' rozumiem tu w sensie stricte programistycznym, obejmującym także jej zasięg i uwzględniającym wszystkie dodatkowe cechy tego pojęcia - jak choćby przesłanianie (name shadowing).
Od razu zastrzegam jednak, żeby nie rozumieć tego zbyt dosłownie. W tym sensie chociażby poniższa pętla:

nie stanowi odpowiedniego przykładu mimo tego, iż zmienna i jest tutaj używana do "nazwania" aż dziesięciu formalnie różnych wartości (). Koncepcyjnie każda z nich jest bowiem tym samym, tj. wartością licznika pętli w danej iteracji.

Wątpliwej słuszności jest dopiero praktyka recyklingu tych samych nazw do różnych celów. Jest tu oczywiście spory margines niepewności jeśli chodzi o definicję słowa 'różny'. Być może dla niektórych osób coś podobnego do poniższego kodu jest już po złej stronie granicy między akceptowalną a niedobrą praktyką:

Inni z kolei mogą nie widzieć nic złego w użyciu jednej zmiennej (np. node) do przekopania się przez pięciokrotnie zagnieżdżoną strukturę XML-a czy JSON-a. Wypada tylko mieć nadzieję, że osoba utrzymująca potem taki kod będzie prezentowała podobny poziom wrażliwości ;-)

Nietrudno zauważyć, że wielokrotne używanie tych samych nazw do różnych celów jest zupełnie możliwe także w językach kompilowanych ze statycznym typowaniem. Dynamiczne typowanie zapewnia jednak o wiele większą "zachętę" do takich praktyk, pozwalając chociażby na takie oto smaczki:

Czy mieszczą się one w kategorii prostoty i czytelności, każdy pewnie oceni indywidualnie. Nie da się jednak ukryć, że kryją one w sobie wielki potencjał zarówno upraszczania, jak i zaciemniania kodu. To wielka moc, z którą naturalnie jest związana wielka odpowiedzialność :)