What happens when you type into a search bar?

Interviewer: Hi.

Me: Hi.

Interviewer: What happens when you type in something into the address bar and hit enter?

Me: How in depth do you want me to go?

Interviewer: Hit me with all you've got.

Me: You asked for it¹:

Typing

The first thing that happens is when your finger lands on the key. How does the keyboard register this keypress? I'm going to talk about the common case seen in most keyboards, especially DIY keyboards since that's what I'm familiar with.

Each key is actually formed by a switch which is quite literally just a switch; it has two pins and when pressed down, connects these two pins electrically. The keyboard contains a microcontroller which is constantly polling each key for a keypress. It pulls one pin high, and waits on the other pin to see if anything comes through. If it detects a voltage on the other pin, the switch is registered as pressed.

Now why does the microcontroller use polling? Most of the time these are actual microcontrollers like ATMega328 with support for interrupts. With interrupts, the programmer can register handlers for various situations like a pin change. The main program execution can continue, or the processor can go to sleep, while waiting for the interrupt condition to trigger. Once the interrupt condition is met, the processor jumps to the interrupt handler and starts execution from there. This is definitely more efficient than continuous polling.

The simple reason is that it does not have enough pins to do so. Interrupts are a passive process, e.g. you are waiting for a pin value to change. That means you cannot be actively toggling pins on and off. So for a microcontroller with n pins, you can only at best be watching n/2 switches (half because each switch has two pins).

To solve the issue with the lack of pins, keyboards generally place the switches on a matrix. Now, instead of addressing each switch with a pair of pins, you address each switch with a pair of row, col pins. Now you can address quadratic number of pins instead. However, this also means you need to be actively scanning for changes. You would do a for row in rows; for col in cols; check(row, col) kind of logic to poll each switch. On a 16MHz microcontroller for around 60 keys, this is sufficiently fast, at least faster than human fingers.

Yes.

USB

Now after the microcontroller gets your input, it has to relay that information to your PC. As mentioned in one of the asides, it has to wait for your PC to poll it before it can start sending. This video by Ben Eater is a very good demonstration and visualization of the data transmission over USB. I'm going to give a very simple summary and mention some interesting parts of the protocol.

USB sends data over differential pairs. What this means is that it has a pair of wires (D+ and D-), and the two states (high, low) and (low, high). Depending on the device mode these two states are either called J/K or K/J. The idea behind this is because if there is some radiation close to the wires, you end up with D+ + noise and D- + noise, and the resultant signal is their difference, which removes the noise at the same time.

Another interesting thing is the lack of a clock signal. If the device just starts off with either wire continually high, the host can start communicating at any point in time. To synchronize clocks, at the start of each packet, a "start of packet" sequence is sent. For <USB 2.0 this sequence is KJKJKJKK. Through this sequence the device syncs its clock to the host and is also able to tell when the actual data transmission is going to start by the trailing KK bits. This start of packet sequence is sent at the start of every packet to re-sync the clocks in case of any drift.

How the clocks get synced is a little beyond me. Apparently the most commonly used technique is something called a phase-locked loop. My understanding is that the phase difference between the signal and internal clocks is used continuously in a feedback loop to adjust the internal clock signal higher or lower. However most time you would just use some generic PHY instead which handles everything for you. For example the ATMega328 I mentioned has this built in. When you use something like the Arduino which is based around a few types of ATMega chips, they also have this built in, which is why you can connect them to your PC easily.

This brings us to another interesting topic which is data encoding. To allow the clocks to sync, there needs to be a sufficient number of transitions in the signal. If there was a huge sequence of Js or Ks being sent, the lack of transitions would mean an absence of reference points for the clocks. There are two schemes in play: Non-Return-To-Zero (NRZ) coding for the waveform and bit-stuffing for the information content.

The reason NRZ is called "non" return-to-zero is because in return-to-zero coding, there would actually be a zero reference we transit to between bits. So sending 1010 would be high zero low zero high zero low zero. In NRZ we do away with the zero level, thus saving bandwidth, but losing the ability to use the zero level for clock syncing. NRZ or more precisely NRZI in the USB2.0 case, means that 0 is represented as a transition and 1 is represented as no transition. This is also why I have not used 1 and 0 prior to this point. This coding scheme may seem a bit odd but let me present another form of NRZ that is more intuitive: let 1 be a transition from low to high or high to high and 0 be a transition from high to low or low to low. There's only four types of transitions and as long as we map them sanely they all do the same thing.

The real reason why we use NRZI instead of the more intuitive mapping of 1 -> high 0 -> low is because NRZI forces one level to always transition. If there were a long sequence of 000000, NRZI will map to JKJKJKJK but the more intuitive NRZ will just be low throughout. The only case where NRZ starts transitioning is when the actual signal transitions, like 10101010 but in that case NRZI is also transitioning. So on every 0 bit we can actually perform synchronization.

To solve the problem with synchronizing 1 bits, USB2.0 employs "bit stuffing". It just inserts an extra 0 after a continuous run of six 1s. USB3.0 uses an encoding scheme called 8b/10b which is a mapping from 8 bit words to 10 bit words, that provides a constraint that the number of 1s and 0s are roughly the same when looking at multiple successive words. This balance of 1s and 0s is important at the speeds that >USB3.0 seeks to attain.

Alright so after this the signal goes through USB to your PC.

Interviewer: Ok so let's just move on to the searching part.

Me: What if your keyboard doesn't use USB?

Interviewer: Ok I don't really give a…

PS/2

No, a PS/2 is not a PlayStation, zoomer.

PS/2 is used in old keyboards where there is usually this purple or green thing with a few pins in it that you plug into your PC. Your PC would usually have two ports, one for the keyboard and another for the mouse. The pins will get bent regularly so you had to throw away the whole keyboard.

The biggest difference between PS/2 and USB is that PS/2 is actually interrupt driven. Here I'm not talking about the keyboard anymore, we've moved on to the communication between PC and the keyboard. So I'm not contradicting myself here — the keyboard uses polling, but the PC uses interrupts for PS/2.

Unlike USB, PS/2 also has a dedicated clock line. Instead of two D+ D- lines, it has a clock and signal line. Low is signalled as 0V, and high is somewhere around 5V.

It's also bidirectional by default unlike USB, where the device has to wait for the host to talk to it. The device can communicate whenever, and when the host wants to talk, it pulls the clock low and keeps it there for awhile.

Another misconception is that PS/2 is faster than USB since it uses interrupts. But the interrupts do not occur immediately and do not arrive instantaneously. So with a max clock rate of 16kHz, and each frame being 11 bits, it takes 0.7ms to send a frame. So that's somewhere around 1kHz. It's not even hard to configure USB to go over this, for example see the Arch Wiki. Although in most cases I think it's not needed at all since your monitor only goes up to 60 or 120Hz or whatever.

Well so PS/2 is super simple.

Interviewer: Ok so now finally we can move onto…

Receiving keystrokes

Here we arrive at the input subsystem of the kernel. I'm just going to talk about Linux but it should map decently to other operating systems.

For PS/2 a keystroke causes an interrupt request. This interrupt is probably handled by a generic PS/2 keyboard driver. The driver registers a interrupt with the CPU, and when the CPU meets an interrupt, it matches the function pointer to the interrupt type. To be more precise, the kernel actually maintains an Interrupt Descriptor Table (IDT) and the driver only registers its handler with the kernel. For USB the situation is much the same, except there is no interrupt handler. The USB driver simply detects the event and raises it to the kernel. The driver in question could be the generic HID driver usbhid or something like usbkbd, and I am actually not sure how to determine which is the one sending the events.

There is a layer above all these called evdev (event device) which exposes a generic character device. If you look under /dev/input/ that's what you're seeing.

There's not much else to say unless we're going to delve into the kernel code. For instance take a look at the Linux kernel docs on creating a input driver.

So what happens next? Let's say the everything has happened and the character device says a key has been pressed. How does the browser know that?

On Linux the browser will most likely be running in some kind of graphical environment. This may be X or Wayland. Something will read the output of evdev to be presented to them. On modern system it is most likely libinput. X will require another driver to interface with libinput since libinput is native to Wayland.

Regardless of what happens, the key now gets registered by the display server. The display server of course maintains some data structure of displayed windows. It sends the keypress event to the active window.

We are going to ignore things like XKB for key layouts, IBus for switching input methods, etc.

Reacting to the keystrokes

Interviewer: This is going to take a while, isn't it.

So now X has sent the event to our application. How does it know what to do?

For example, if we are talking about X, you would use Xlib in an event loop. Wow, actual code:

#include <X11/Xlib.h>
#include <X11/keysym.h>

while (1) {
    XNextEvent(display, &event);

    if (event.type == KeyPress) {
        KeySym keysym = XLookupKeysym(&event.xkey, 0);
        printf("Key pressed: %s\n", XKeysymToString(keysym));
    }
}

So you just do a blocking wait till X sends you a key. Of course, we are skipping some steps here. X is called X "server" because before this you actually have to negotiate some kind of connection with it. However any modern GUI toolkit like GTK or QT will perform these steps for you.

In any case, our browser finally receives the event and now reacts to it!

Interviewer: Finally, let's talk about the DNS requests and…

Now it has to render the character. Alright, I'll keep it brief to hide my incompetence.

First it has to rasterize the glyph from the font. Fonts, as you might know, are not defined as an array of pixels (bitmaps), which is why they don't get blurry if you zoom in. A huge font doesn't get jagged edges like you would if you just zoomed into a jpeg screenshot (an array of pixels) of the font. That's because most modern fonts are vector fonts, and each glyph is defined by a set of equations that describe how to draw them. So to begin rendering to pixels, the application has to first convert this keystroke into pixels first.

I have no idea how it does that but it does that. There are also absolutely mind boggling things here like subpixel anti-aliasing and kerning etc. that I'm just going to pretend are not important and skip. I am also going to completely skip problems with scripts like Arabic or Vietnamese where you can stack or extend characters arbitrarily tall or wide.

Finally you would put this glyph onto the screen. You can do all of this with just Xlib if you want, but there are a whole bunch of libraries and tools just to do this. For example Harfbuzz is a popular text renderer, and Cairo is a popular 2D graphics library.

After pressing return

Alright so you hit enter and the browser receives it and starts processing your query. It looks at the URL you provided and checks for a valid top level domain (TLD) ².

Regardless of whether the URL is valid or not, the browser will either form a search query or go to the page itself. In the case of a search query, it is itself another page just with some search parameters. So let's just talk about visiting pages. And let's ignore caching.

Visiting pages

First the browser is going to perform DNS resolution to find the IP address behind the link. Usually the browser has its own cache, which it looks up, failing which it will query the OS.

There is a system library function on Linux called getaddrinfo to help with address resolution. First, this looks at the hosts file. On Linux it is at /etc/hosts, and on Windows it is somewhere under C:\Windows\System32 probably. The format is quite straightforward, just a list of IP to hostname pairs.

In the case when the host is not in the hosts file, actual DNS resolution begins. Before that even happens, the system finds the IP of the DNS server it needs to contact. Sometimes this is a local address, especially if you have setup a DNS server on your router or some other device. This is common for users who use things like OpenWRT or PiHole. Or it could be a remote server like Google's 8.8.8.8 or Cloudflare's 1.1.1.1 or Quad9's 9.9.9.9, or your ISP's default.

How does the OS even get the address of the DNS server? The first case which is rarer at home is through manual configuration. The more common case is by being advertised through DHCP. If your system uses DHCP to get an IP from some server, most likely your router, it can also advertise a list of DNS servers at the same time. By default this is most likely going to be something your ISP has set up, although you can override this on some routers.

Now we have the DNS server's IP, we need to find its MAC address. This is because Ethernet is a layer 2 protocol, and it uses MAC to address individual devices.

Finding the MAC address is achieved with something called the Address Resolution Protocol (ARP). Your PC will first check its ARP cache. If there's no matching IP address, your PC will send out a broadcast MAC packet (destination FF:FF:FF:FF:FF:FF) containing the target IP it wants to query. This routes the packet to all devices on the network. The device with the target IP upon receiving this packet, then replies by sending a similar packet but now to the PC, containing its own MAC address. You can use the command arp to run an ARP query and see its result.

If the DNS address is on the local subnet, the ARP query will be for this address directly; otherwise the ARP query will be for the default gateway, most likely your router. The latter scenario occurs for example when you are using a public DNS like 1.1.1.1 or 8.8.8.8. In that case, your router will have to route traffic to the Internet.

Let's ignore that case first and just imagine the DNS server has received the query. It is also going to have a cache, which it checks. If there is no match, it will start querying the Root Server .. Because there is nothing above the Root Servers to help resolve the Root Servers' addresses, the IPs for the Root Servers have to be hardcoded into every DNS server. Anyway, it queries one of the Root Servers ³ for the Top Level Domain (TLD) server, maybe .com or .net (again if it's not already cached). After it gets the address of the TLD nameserver, it will query it for the authoritative nameserver of the full host, like google.com. Once it gets the address of the authoritative nameserver, it queries it again, which results in things like the A record that contains the actual IP address, the CNAME record that contains an alias, the MX record that contains the address of a mail server, etc.

You can use the nslookup or dig command to send a DNS query to a default or specified nameserver and view the response.

Routing the query

Now the browser has the IP address of the website it has to go to. It now needs to communicate with this remote server. It is going to send some packets, let's talk about routing first, and the actual packets later on.

Your browser is going to be in a Local Area Network (LAN). The remote server hosting the website is in what is called the Wide Area Network (WAN) ⁴. The browser needs to reach this host, and the doorway is the default gateway. The default gateway IP address is advertised by DHCP, although it can be set manually as well.

So the packet being sent out will have the MAC address of the default gateway (usually your router) and the IP address of the remote server. Upon receiving this packet, your router will examine the destination IP to determine how to forward it ⁵.

Here is where it starts getting a little hairy, and I am not too clear of the details either. When your router first receives the packet, it will be on one of its LAN interfaces. The router will most likely have some kind of pre-configured static routing rule internally to route packets not destined for the local subnet on to its WAN interface. The WAN interface most likely faces your modem or Optical Network Terminal (ONT). The packet is then routed to them, and they will then route it again based on their internal routing tables, and so on.

At the ISP level routing becomes considerably more challenging. Each ISP (but not restricted to only ISPs) forms an Autonomous System (AS). ASes communicate within themselves and among each other using a protocol called the Border Gateway Protocol (BGP). There are two forms, iBGP and eBGP for internal and external use. iBGP can be used to connect routers within an AS, although other protocols can also be used in its place. eBGP is used to communcate with other ASes. BGP is mainly used to exchange routing information. Information exchanged include things like hop count, reachability, etc. BGP operates on top of TCP.

There are some organizations that operate some part of the Internet backbone. The ISP routes the packet onto the backbone, guided by the routing information shared by BGP, and the packet goes on and on till perhaps it hits some other ISP in another country, and finally reaches the destination host. Backbones are generally large fibre optic cables or undersea cables and repeaters and what not. Usually you have to pay to route traffic through these routes, as expected.

On the way there is also this thing called the Time To Live (TTL) field in the packet header. This prevents any infinite loops from occurring. At each hop, this number is decremented by 1. If it hits 0, the packet is discarded. There is a utility called traceroute that sends packets with TTL starting from 1 to some maximum value, to a specified destination. When the TTL hits 0, the router handling the packet sends an error packet back, and that is how traceroute is able to find where every hop landed step by step.

Connections

Now that we are done with the routing stuff, let's move on to what is actually being sent.

The browser most likely is going to send a HTTP GET request which is going to use TCP. For system calls please also refer to their manpages for more details.

1. Client opens a socket⁶. On POSIX system its done with the socket system call: sock = socket(AF_INET, SOCK_STREAM, 0); and returns a file descriptor of the socket. AF_INET means communication will be based on IPv4, and SOCK_STREAM means TCP. The other alternative is SOCK_DGRAM for UDP.

2. Connect to the remote server with the connect system call.

     struct sockaddr_in addr = {0};
     addr.sin_family = AF_INET;
     addr.sin_port = htons(8080);
     addr.sin_addr.s_addr = inet_addr("172.253.118.101");
   
     connect(sock, (struct sockaddr *)&addr, sizeof(addr))
   

   The type casting is because connect accepts a generic struct type as its second parameter that is interpreted depending on the socket type. In our case sockaddr_in is suitable for IPv4 use. The in_addr_t inet_addr(const char *cp) function converts the IP address as a string into bytes (in_addr_t is typedefed to uint32 on my system). htons is used here to convert from little endian to big endian.

3. Next we use the send system call to send a request. send(sock, buffer, strlen(buffer), 0);. It is also possible to use write and sock as the file descriptor.
4. Then we use the recv system call to receive a response. recv(sock, buffer, sizeof(buffer), 0);. Again it is also possible to use read.

Let's ignore all the TCP and HTTP stuff for a moment and look at a summary of everything so far:

#include <arpa/inet.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>

#define BUFSIZE 1024

int main() {
  char *host = "httpforever.com";
  struct addrinfo *res = {0};

  int sock;
  sock = socket(AF_INET, SOCK_STREAM, 0);
  if (sock < 0) {
    perror("Socket error");
    exit(1);
  }

  if (getaddrinfo(host, "http", NULL, &res)) {
    perror("getaddrinfo failed");
    exit(1);
  }

  if (connect(sock, res->ai_addr, res->ai_addrlen) == 0) {
    puts("Connected to server");
  } else {
    perror("connect failed");
    exit(1);
  }

  char buffer[BUFSIZE];
  snprintf(buffer, BUFSIZE,
           "GET / HTTP/1.0\r\nHost: %s\r\nConnection: close\r\n\r\n", host);

  printf("Send:\n%s\n", buffer);
  if (send(sock, buffer, strlen(buffer), 0) < 0) {
    perror("send error");
    exit(1);
  }

  bzero(buffer, BUFSIZE);
  if (recv(sock, buffer, sizeof(buffer), 0) == -1) {
    perror("recv error");
    exit(1);
  }
  printf("Server response:\n%s\n", buffer);

  close(sock);
  puts("Connection closed.");

  return 0;
}

This code uses everything we have covered so far. It calls getaddrinfo to query the DNS for the address of httpforever.com, then opens a connection to this server, and then sends a certain HTTP request to get its homepage. It then reads the response and prints it to stdout. Running this code gives

Connected to server
Send:
GET / HTTP/1.0
Host: httpforever.com
Connection: close


Server response:
HTTP/1.1 200 OK
... a lot of headers

<!DOCTYPE HTML>
... more html below

In the following section we will talk about the protocols used behind the scenes.

Interviewer: This is the first time that I've heard of sections in a candidate's reply.

TCP

The initial connection between client and server is set up through a three-way handshake. It is called three-way because there are three steps.

1. The client generates an Initial Sequence Number (ISN). It sends a TCP packet with the SYN flag and its ISN in the header.
2. The server receives the packet, and if it decides to connect with the client, it will also generate a separate ISN, and send a packet back to the client. This packet will contain its ISN, the client's ISN + 1 as the acknowledgement field, and both the SYN and ACK bits set in the header.
3. The client replies with an ACK again, with acknowledgement set to the server's ISN + 1.

Some points: The ISN is not sent all the time. It is only sent when the SYN bit is set. Future communications only need the acknowledgement number. The acknowledgement is always 1 plus the previous sequence number. This helps TCP keep packets in order. Packets may arrive out of order but the system will rearrange them back in order using the sequence number.

Future communications will occur by the sender incrementing its sequence number and then sending a certain amount of bytes. Then the recipient sends an ACK back with the sequence number + 1. If an ACK isn't received within a certain timeout period, the sender retransmits the packet. There are also some more details here like network conjestion and window sizes etc. but basically that's it.

When the connection is to be closed, either party sends a FIN. The recipient first ACKs the FIN, then after perhaps doing some cleanup or what not, also sends a FIN. The initiator then ACKs this FIN, and we are done.

HTTP

Notice in our code example above we have sent a simple HTTP GET request for the index page /. This happens after the TCP connection is established. A HTTP packet generally takes the following structure:

<method> <request-target> <protocol>
<headers>
-- empty line --
<body>

Newlines can be represented by just \n although the specs state that they should be \r\n. Best to stay on the safe side.

Also note the two newlines after the headers. The end of the headers is represented by \r\n\r\n. If you forgot to add the second newline, the send will never complete as the server will be hanging waiting for the next line of the headers to come in.

The body is used for situations like POST requests. GET requests cannot have a body. In fact, only PATCH, PUT and POST can have bodies. For us, we just leave it empty.

Also, regarding encoding: for HTTP1.1 ASCII is used for everything but the body, and anything can be used for the body. To use a different encoding in the body, we have to specify charset in the header.

In our example the server responded with a 200 OK along with the HTML payload, and we are done. However, if you tried running the example code with something like firefox.com instead⁷, you will receive

HTTP/1.0 302 Found
Cache-Control: private
Location: https://firefox.com:443/
Content-Length: 0
Date: Mon, 06 Jan 2025 05:59:45 GMT
Content-Type: text/html; charset=UTF-8

302 is a redirect to the address in the Host field. This brings us to our next topic, HTTPS and TLS.

HTTPS and TLS

HTTPS is the secured version of HTTP, hence the S. HTTPS communicates over TLS⁸. TLS both identifies the server and encrypts the traffic being sent across the connection.

TLS, unlike HTTP, is not a ASCII based protocol. It is more like TCP where the headers are raw bytes so keep that in mind (although ASCII is also raw bytes hmmmm!).

Furthermore, TLS is more like a negotiation protocol and doesn't actually perform the encryption. What I mean is that there are MANY ways to do encryption (each called a cipher) and TLS doesn't explicitly mandate which one to use. However, there are only a few that are supported. Hence, the first thing that the client does when connecting to a server is to present a list of ciphers (technically cipher suites)that it supports.

Each cipher suite is a tuple, but mainly they contain an asymmetric-key (or public key) cipher and symmetric-key cipher, and a hash but let's ignore the hash. The asymmetric-key cipher is used in Diffie-Hellman key exchange to generate a shared secret between the two parties using their public keys. Then the shared secret is used to encrypt the plaintext message using the symmetric-key cipher. The other party can decrypt the message with the shared secret and the same symmetric-key cipher.

After agreeing on the algorithms they will be using for the rest of the session, the server also sends over a certificate. This certificate is what you see in your browser's address bar; sometimes its a green symbol with the organization's name, sometimes its a symbol of a lock saying "connection is secure".

To create the certificate, start with a plaintext message containing the server's organization name, hostname, and some other parameters. Then, this is given to a Certificate Authority (CA) like Let's Encrypt or Cloudflare. They will form a signature with your message by hashing and encrypting the hash with their private key. The message, public key, signature, and some metadata forms the certificate. Of course this process is done beforehand, and the server uses the same certificate for all TLS connections.

The client just needs to decrypt the certificate with the attached public key and verify that the result matches the hash of the plaintext message. Another important check is the chain of trust. CAs are the base of the chain of trust. Anything signed by them is trust-worthy since they have to undergo many auditing procedures before being admitted as a CA. As a result, their public keys are installed in many browsers and operating systems by default. Anything signed by whatever they signed is also trustworthy by extension. The reason behind this is with intermediate CAs: it is hard to recall the public key if a private key of a CA is leaked. You would have to patch all these servers and browsers worldwide. Instead, all signing is performed with an intermediate CA generated by the root CA. Then, you can just invalidate the intermediate CA (there is a protocol called OCSP to do this) instead if something goes wrong, and generate new ones. Thus, the server will not only send their certificate, but all intermediate certificates in the response for the client to check down the chain.

In any case, while this is happening the server calculates and sends a public and private keypair. If the client is also satisfied, it will do the same. Both parties can compute a shared secret through key exchange, and future communications from now on will be encrypted with this shared secret.

In TLS1.3, there is a slight optimization here to reduce one round trip from the negotiation. Instead of sending a list of ciphers, agreeing, then proceeding, the client will send over a list of ciphers together with the required public keys and other information. Thus the server doesn't need to wait for it to reply the second time with the keys: it can just reply with which cipher it chose from the list, along with its keys and certificates.

There are also some other extensions like session resume etc. that I didn't cover. In short, session resume allows both parties to continue with a previously negotiated set of keys instead of restarting the whole process.

HTML et al.

To be honest I think that's about all that's interesting. I was going to talk about HTML and CSS and JS, but I feel like they aren't too low level to be interesting.

The browser just uses HTML to construct the DOM tree and uses CSS to position it. Although creating a HTML parser and CSS engine is really hard, I don't think there's too much to talk about it unless we actually went into the HTML and CSS rules, like inline or block positioning, etc.

Also for JS, well the way its executed differs across implementations, and most browsers probably just rely on V8 or something.

There are also some further topics like sandboxing.