curl bitsets

6 min read Original article ↗

In my last blog post I wrote about why linked lists are often not a good idea. In this post I want to present how we replaced some of curl’s lists with an array and bitsets.

The Problems

curl has two main APIs to perform internet transfers: the easy and the multi set of functions. If you want to do just a single transfer at a time, the easy interface is the right one for you. If you need to do several transfers in parallel or want connection reuse, the multi interface is best.

A single multi handle can hold thousands of easy transfers at a time and progress them in an unblocking manner. Transfers may wait on a socket for data to arrive/send or transfers wait on other transfers to complete.

For the multi handle, a transfer is either pending, processing or in msgsent state (the transfer is done, waiting for the application to pick it up again). They move between these states over their lifetime:

  • a newly added transfer is put in processing state
  • if processing cannot get a connection for the transfer it becomes pending
  • when conditions change pending transfers enter processing again
  • when a transfer finishes, it becomes msgsent.

Until spring last year, the multi handle kept three linked lists for these states. Moving transfers between lists had to happen while iterating over them, leading to the problems I described in my previous post. Changing linked lists while iterating is tricky to do right.

Another source of problems where transfer dependencies. When you use Doh (DNS over HTTPS), curl creates internal transfer to talk to the DNS server. When the DoH transfer has finished (or failed), it needs to notify the originating transfer. When the originating transfer is removed by the application, it needs to also kill its DoH transfers (if it has any).

For this, transfer were pointing to each other with a C pointer. If the code did anything wrong, pointers became dangling, causing undefined behaviour or crashes.

What to do?

Transfer Table

We decided to place all transfers of a multi handle into a single table, an array of pointers. That would be the only place where we store the address of a transfer. The index in this table can then be used to track dependencies.

This works like process or file ids in your operating system. The OS keeps its data structures internally and hands out a number to refer to a particular process or file. If someone uses an id that no longer exists, an error is returned (but your OS does not crash).

We decided that an uint32_t is a sufficiently large transfer identifier. When adding a transfer to a multi handle, an id is assigned to it from a free table entry. When removing the transfer, its table entry is cleared and no other pointers to it exist any more.

The table may need growing on additions and is kept at least 25% free so transfer ids are not immediately reused. Keeping track of 1000 transfers on a 64-bit system uses a single 8kb memory chunk for the table. Seems fine.

Transfer State

In theory, we could make the multi’s pending, processing and msgsent state just a member of the transfer, like transfer->multi_state. But that would mean scanning the complete table every time we need to iterate over a specific state. That may be ok when you expect to visit almost all table entries. But for rare states, this is too costly.

It is common to have only a single transfer in pending and scanning the complete table to find it would be slow. We needed a good way to store sets of transfer identifiers.

Bit Sets

Bit sets are a wonderful data structure if you have a fixed interval of numbers to manage:

  • With a uint64_t set[16] you can manage the numbers [0, 1023]. Cheap.
  • Operations are constant time. To see if i is in the set, you look at bit i%64 in set[i/64]. Same for adding/removing a number.
  • Iterations are fast. You ask the set for the first (smallest) number initially and then for the next number higher than the last. The last number is the iteration state by itself.
  • Iterations are safe and fair. Changes to the set during iteration are no problem. Even changing the set capacity is a non-issue.
  • Most CPUs have instructions for bit operations the set needs and compilers expose primitives to use them. For example for counting the number of 1 bits in a uint64_t, or for determining the number of lower, e.g. trailing 0 bits.

The multi handle now has bit sets for pending, processing and msgsent. Moving a transfer from one state to another clears the bit in the old set and sets it in the new one. Removing a transfer clears the bit in all sets.

This all can be done at any time. We no longer have to watch out for transfer state changes or additions/removals during iteration.

Memory

Besides the ease in handling of common operations, the overall memory use for managing transfers in a multi handle was reduced.

In addition, the memory used is no longer scattered around in the heap. Table and bit sets own a chunk of memory each and often access it in consecutive order which CPU caches just love.

Sparse Bit Sets

In addition to the multi states described above, there are other places where curl needs to manage a “set of transfers”. When it operates event driven it needs to track the transfers that are interested in a socket. When an event on the socket happens, all transfers that wait on that need to be processed.

Compared to the overall amount of transfers, the number per socket is often just one. On loaded HTTP/2+3 connections maybe up to one hundred. Keeping a full bit set for each socket is a waste.

We use sparse bit sets for this that use less memory at higher cost of operations.

Code

You can find our code for these data structures at uint-table.c, uint-bset.c and uint-spbset.c.

Design Space

Can you make use of this design in your project? The basic restriction is that you have a limited amount of things to manage (or at least converging on a limit over time). Then you can assign numbers from a comparatively small interval and manage those in bit sets.

If the amount of things changes rapidly, or if they are very temporary, it might not be worth it. But if you need to track them over some time and manage changing subsets of them, I’d say it’s worth investigating.