curl bitsets | icing's blog

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

The Problems

curl has two main APIs to perform internet transfers: the easy and the<br>multi set of functions. If you want to do just a single transfer at a time,<br>the easy interface is the right one for you. If you need to do several<br>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<br>progress them in an unblocking manner. Transfers may wait on a socket for<br>data to arrive/send or transfers wait on other transfers to complete.

For the multi handle, a transfer is either pending, processing or in<br>msgsent state (the transfer is done, waiting for the application to pick<br>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<br>states. Moving transfers between lists had to happen while iterating<br>over them, leading to the problems I described in<br>my previous post. Changing linked lists while<br>iterating is tricky to do right.

Another source of problems where transfer dependencies. When you use Doh<br>(DNS over HTTPS), curl creates internal transfer to talk to the DNS server.<br>When the DoH transfer has finished (or failed), it needs to notify the<br>originating transfer. When the originating transfer is removed by the<br>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<br>code did anything wrong, pointers became dangling, causing undefined<br>behaviour or crashes.

What to do?

Transfer Table

We decided to place all transfers of a multi handle into a single table, an<br>array of pointers. That would be the only place where we store the address<br>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.<br>The OS keeps its data structures internally and hands out a number to<br>refer to a particular process or file. If someone uses an id that no longer<br>exists, an error is returned (but your OS does not crash).

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

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

Transfer State

In theory, we could make the multi&rsquo;s pending, processing and msgsent<br>state just a member of the transfer, like transfer->multi_state. But<br>that would mean scanning the complete table every time we need to iterate<br>over a specific state. That may be ok when you expect to visit almost<br>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<br>complete table to find it would be slow. We needed a good way to store<br>sets of transfer identifiers.

Bit Sets

Bit sets are a wonderful data structure if you have a fixed interval of<br>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<br>i%64 in set[i/64]. Same for adding/removing a number.

Iterations are fast. You ask the set for the first (smallest) number<br>initially and then for the next number higher than the last. The last<br>number is the iteration state by itself.

Iterations are safe and fair. Changes to the set during iteration are<br>no problem. Even changing the set capacity is a non-issue.

Most CPUs have instructions for bit operations the set needs and<br>compilers expose primitives to use them. For example for counting<br>the number of 1 bits in a uint64_t, or for determining the number<br>of lower, e.g. trailing 0 bits.

The multi handle now has bit sets for pending, processing and msgsent.<br>Moving a transfer from one state to another clears the bit in the old set<br>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<br>transfer state changes or additions/removals during iteration.

Memory

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

In addition, the memory used is no longer scattered around in the heap.<br>Table and bit sets own a chunk of memory each and...