From 909af1a43b5a7fed8b5a4ca145e39f46b2f50325 Mon Sep 17 00:00:00 2001 From: Stefan Eissing Date: Tue, 25 Mar 2025 09:47:40 +0100 Subject: [PATCH] multi: do transfer book keeping using mid Change multi's book keeping of transfers to no longer use lists, but a special table and bitsets for unsigned int values. `multi-xfers` is the `uint_tbl` where `multi_add_handle()` inserts a new transfer which assigns it a unique identifier `mid`. Use bitsets to keep track of transfers that are in state "process" or "pending" or "msgsent". Use sparse bitsets to replace `conn->easyq` and event handlings tracking of transfers per socket. Instead of pointers, keep the mids involved. Provide base data structures and document them in docs/internal: * `uint_tbl`: a table of transfers with `mid` as lookup key, handing out a mid for adds between 0 - capacity. * `uint_bset`: a bitset keeping unsigned ints from 0 - capacity. * `uint_spbset`: a sparse bitset for keeping a small number of unsigned int values * `uint_hash`: for associating `mid`s with a pointer. This makes the `mid` the recommended way to refer to transfers inside the same multi without risk of running into a UAF. Modifying table and bitsets is safe while iterating over them. Overall memory requirements are lower as with the double linked list apprach. Closes #16761 --- .github/scripts/spellcheck.words | 1 + docs/Makefile.am | 2 + docs/internals/MID.md | 72 ++++ docs/internals/UINT_SETS.md | 131 ++++++++ include/curl/system.h | 4 + lib/Makefile.inc | 6 + lib/asyn.h | 5 +- lib/conncache.c | 9 +- lib/doh.c | 22 +- lib/doh.h | 17 +- lib/easy.c | 18 +- lib/hash_offt.c | 203 +++++++++++- lib/hash_offt.h | 34 +- lib/http2.c | 24 +- lib/multi.c | 541 +++++++++++++++++++------------ lib/multi_ev.c | 122 ++++--- lib/multi_ev.h | 7 +- lib/multihandle.h | 22 +- lib/multiif.h | 13 +- lib/share.c | 2 + lib/uint-bset.c | 238 ++++++++++++++ lib/uint-bset.h | 114 +++++++ lib/uint-spbset.c | 273 ++++++++++++++++ lib/uint-spbset.h | 99 ++++++ lib/uint-table.c | 214 ++++++++++++ lib/uint-table.h | 101 ++++++ lib/url.c | 58 ++-- lib/urldata.h | 11 +- lib/vquic/curl_msh3.c | 16 +- lib/vquic/curl_ngtcp2.c | 26 +- lib/vquic/curl_osslq.c | 38 +-- lib/vquic/curl_quiche.c | 34 +- tests/data/Makefile.am | 2 +- tests/data/test3211 | 22 ++ tests/data/test3212 | 22 ++ tests/data/test3213 | 22 ++ tests/http/test_07_upload.py | 3 +- tests/unit/Makefile.inc | 9 +- tests/unit/unit3211.c | 153 +++++++++ tests/unit/unit3212.c | 136 ++++++++ tests/unit/unit3213.c | 127 ++++++++ 41 files changed, 2551 insertions(+), 422 deletions(-) create mode 100644 docs/internals/MID.md create mode 100644 docs/internals/UINT_SETS.md create mode 100644 lib/uint-bset.c create mode 100644 lib/uint-bset.h create mode 100644 lib/uint-spbset.c create mode 100644 lib/uint-spbset.h create mode 100644 lib/uint-table.c create mode 100644 lib/uint-table.h create mode 100644 tests/data/test3211 create mode 100644 tests/data/test3212 create mode 100644 tests/data/test3213 create mode 100644 tests/unit/unit3211.c create mode 100644 tests/unit/unit3212.c create mode 100644 tests/unit/unit3213.c diff --git a/.github/scripts/spellcheck.words b/.github/scripts/spellcheck.words index 80f323ba80..17b891ca1a 100644 --- a/.github/scripts/spellcheck.words +++ b/.github/scripts/spellcheck.words @@ -63,6 +63,7 @@ BearSSL Benoit BeOS bitmask +bitset bitwise Björn Bjørn diff --git a/docs/Makefile.am b/docs/Makefile.am index 084d40b798..0c92dd8a33 100644 --- a/docs/Makefile.am +++ b/docs/Makefile.am @@ -51,6 +51,7 @@ INTERNALDOCS = \ internals/DYNBUF.md \ internals/HASH.md \ internals/LLIST.md \ + internals/MID.md \ internals/MQTT.md \ internals/MULTI-EV.md \ internals/NEW-PROTOCOL.md \ @@ -59,6 +60,7 @@ INTERNALDOCS = \ internals/SPLAY.md \ internals/STRPARSE.md \ internals/TLS-SESSIONS.md \ + internals/UINT_SETS.md \ internals/WEBSOCKET.md EXTRA_DIST = \ diff --git a/docs/internals/MID.md b/docs/internals/MID.md new file mode 100644 index 0000000000..17b11ea792 --- /dev/null +++ b/docs/internals/MID.md @@ -0,0 +1,72 @@ + + +# Multi Identifiers (mid) + +All transfers (easy handles) added to a multi handle are assigned +a unique identifier until they are removed again. The multi handle +keeps a table `multi->xfers` that allow O(1) access to the easy +handle by its `mid`. + +References to other easy handles *should* keep their `mid`s instead +of a pointer (not all code has been converted as of now). This solves +problems in easy and multi handle life cycle management as well as +iterating over handles where operations may add/remove other handles. + +### Values and Lifetime + +An `mid` is an `unsigned int`. There are two reserved values: + +* `0`: is the `mid` of an internal "admin" handle. Multi and share handles + each have their own admin handle for maintenance operations, like + shutting down connections. +* `UINT_MAX`: the "invalid" `mid`. Easy handles are initialized with + this value. They get it assigned again when removed from + a multi handle. + +This makes potential range of `mid`s from `1` to `UINT_MAX - 1` *inside +the same multi handle at the same time*. However, the `multi->xfers` table +reuses `mid` values from previous transfers that have been removed. + +`multi->xfers` is created with an initial capacity. At the time of this +writing that is `16` for "multi_easy" handles (used in `curl_easy_perform()` +and `512` for multi handles created with `curl_multi_init()`. + +The first added easy handle gets `mid == 1` assigned. The second one receives `2`, +even when the fist one has been removed already. Every added handle gets an +`mid` one larger than the previously assigned one. Until the capacity of +the table is reached and it starts looking for a free id at `1` again (`0` +is always in the table). + +When adding a new handle, the multi checks the amount of free entries +in the `multi->xfers` table. If that drops below a threshold (currently 25%), +the table is resized. This serves two purposes: one, a previous `mid` is not +reused immediately and second, table resizes are not needed that often. + +The table is implemented in `uint-table.[ch]`. More details in [`UINT_SETS`](UINT_SETS.md). + +### Tracking `mid`s + +There are several places where transfers need to be tracked: + +* the multi tracks `process`, `pending` and `msgsent` transfers. A transfer + is in at most one of these at a time. +* connections track the transfers that are *attached* to them. +* multi event handling tracks transfers interested in a specific socket. +* DoH handles track the handle they perform lookups for (and vice versa). + +There are two bitset implemented for storing `mid`s: `uint_bset` and `uint_spbset`. +The first is a bitset optimal for storing a large number of unsigned int values. +The second one is a "sparse" variant good for storing a small set of numbers. +More details about these in [`UINT_SETS`](UINT_SETS.md). + +A multi uses `uint_bset`s for `process`, `pending` and `msgsent`. Connections +and sockets use the sparse variant as both often track only a single transfer +and at most 100 on an HTTP/2 or HTTP/3 connection/socket. + +These sets allow safe iteration while being modified. This allows a multi +to iterate over its "process" set while existing transfers are removed +or new ones added. diff --git a/docs/internals/UINT_SETS.md b/docs/internals/UINT_SETS.md new file mode 100644 index 0000000000..38509e308d --- /dev/null +++ b/docs/internals/UINT_SETS.md @@ -0,0 +1,131 @@ + + +# Unsigned Int Sets + +The multi handle tracks added easy handles via an unsigned int +it calls an `mid`. There are four data structures for unsigned int +optimized for the multi use case. + +## `uint_tbl` + +`uint_table`, implemented in `uint-table.[ch]` manages an array +of `void *`. The unsigned int are the index into this array. It is +created with a *capacity* which can be *resized*. The table assigns +the index when a `void *` is *added*. It keeps track of the last +assigned index and uses the next available larger index for a +subsequent add. Reaching *capacity* it wraps around. + +The table *can not* store `NULL` values. The largest possible index +is `UINT_MAX - 1`. + +The table is iterated over by asking for the *first* existing index, +meaning the smallest number that has an entry, if the table is not +empty. To get the *next* entry, one passes the index of the previous +iteration step. It does not matter if the previous index is still +in the table. Sample code for a table iteration would look like this: + +```c +unsigned int mid; +void *entry; + +if(Curl_uint_tbl_first(tbl, &mid, &entry)) { + do { + /* operate on entry with index mid */ + } + while(Curl_uint_tbl_next(tbl, mid, &mid, &entry)); +} + +``` + +This iteration has the following properties: + +* entries in the table can be added/removed safely. +* all entries that are not removed during the iteration are visited. +* the table may be resized to a larger capacity without affecting visited entries. +* entries added with a larger index than the current are visited. + +### Memory + +For storing 1000 entries, the table would allocate one block of 8KB on a 64-bit system, +plus the 2 pointers and 3 unsigned int in its base `struct uint_tbl`. A resize +allocates a completely new pointer array, copy the existing entries and free the previous one. + +### Performance + +Lookups of entries are only an index into the array, O(1) with a tiny 1. Adding +entries and iterations are more work: + +1. adding an entry means "find the first free index larger than the previous assigned + one". Worst case for this is a table with only a single free index where `capacity - 1` + checks on `NULL` values would be performed, O(N). If the single free index is randomly + distributed, this would be O(N/2). +2. iterating a table scans for the first not `NULL` entry after the start index. This + makes a complete iteration O(N) work. + +In the multi use case, point 1 is remedied by growing the table so that a good chunk +of free entries always exists. + +Point 2 is less of an issue for a multi, since it does not really matter when the +number of transfer is relatively small. A multi managing a larger set needs to operate +event based anyway and table iterations rarely are needed. + +For these reasons, the simple implementation was preferred. Should this become +a concern, there are options like "free index lists" or, alternatively, an internal +bitset that scans better. + +## `uint_bset` + +A bitset for unsigned integers, allowing fast add/remove operations. It is initialized +with a *capacity*, meaning it can store only the numbers in the range `[0, capacity-1]`. +It can be *resized* and safely *iterated*. `uint_bset` is designed to operate in combination with `uint_tbl`. + +The bitset keeps an array of `curl_uint64_t`. The first array entry keeps the numbers 0 to 63, the +second 64 to 127 and so on. A bitset with capacity 1024 would therefore allocate an array +of 16 64-bit values (128 bytes). Operations for an unsigned int divide it by 64 for the array index and then check/set/clear the bit of the remainder. + +Iterator works the same as with `uint_tbl`: ask the bitset for the *first* number present and +then use that to get the *next* higher number present. Like the table, this safe for +adds/removes and growing the set while iterating. + +### Memory + +The set only needs 1 bit for each possible number. +A bitset for 40000 transfers occupies 5KB of memory. + +## Performance + +Operations for add/remove/check are O(1). Iteration needs to scan for the next bit set. The +number of scans is small (see memory footprint) and, for checking bits, many compilers +offer primitives for special CPU instructions. + +## `uint_spbset` + +While the memory footprint of `uint_bset` is good, it still needs 5KB to store the single number 40000. This +is not optimal when many are needed. For example, in event based processing, each socket needs to +keep track of the transfers involved. There are many sockets potentially, but each one mostly tracks +a single transfer or few (on HTTP/2 connection borderline up to 100). + +For such uses cases, the `uint_spbset` is intended: track a small number of unsigned int, potentially +rather "close" together. It keeps "chunks" with an offset and has no capacity limit. + +Example: adding the number 40000 to an empty sparse bitset would have one chunk with offset 39936, keeping +track of the numbers 39936 to 40192 (a chunk has 4 64-bit values). The numbers in that range can be handled +without further allocations. + +The worst case is then storing 100 numbers that lie in separate intervals. Then 100 chunks +would need to be allocated and linked, resulting in overall 4 KB of memory used. + +Iterating a sparse bitset works the same as for bitset and table. + +## `uint_hash` + +At last, there are places in libcurl such as the HTTP/2 and HTTP/3 protocol implementations that need +to store their own data related to a transfer. `uint_hash` allows then to associate an unsigned int, +e.g. the transfer's `mid`, to their own data. + +This is just a variation of `hash_offt` that can associate data with a `connection_id`. Which +is a specialization of the generic `Curl_hash`. diff --git a/include/curl/system.h b/include/curl/system.h index 00bd638ce4..f1c2719cfe 100644 --- a/include/curl/system.h +++ b/include/curl/system.h @@ -336,6 +336,8 @@ # define CURL_FORMAT_CURL_OFF_TU "llu" # define CURL_SUFFIX_CURL_OFF_T LL # define CURL_SUFFIX_CURL_OFF_TU ULL +# define CURL_POPCOUNT64(x) __builtin_popcountll(x) +# define CURL_CTZ64(x) __builtin_ctzll(x) # elif defined(__LP64__) || \ defined(__x86_64__) || defined(__ppc64__) || defined(__sparc64__) || \ defined(__e2k__) || \ @@ -346,6 +348,8 @@ # define CURL_FORMAT_CURL_OFF_TU "lu" # define CURL_SUFFIX_CURL_OFF_T L # define CURL_SUFFIX_CURL_OFF_TU UL +# define CURL_POPCOUNT64(x) __builtin_popcountl(x) +# define CURL_CTZ64(x) __builtin_ctzl(x) # endif # define CURL_TYPEOF_CURL_SOCKLEN_T socklen_t # define CURL_PULL_SYS_TYPES_H 1 diff --git a/lib/Makefile.inc b/lib/Makefile.inc index c8689a578c..0b034df92e 100644 --- a/lib/Makefile.inc +++ b/lib/Makefile.inc @@ -236,6 +236,9 @@ LIB_CFILES = \ timediff.c \ timeval.c \ transfer.c \ + uint-bset.c \ + uint-spbset.c \ + uint-table.c \ url.c \ urlapi.c \ version.c \ @@ -376,6 +379,9 @@ LIB_HFILES = \ timediff.h \ timeval.h \ transfer.h \ + uint-bset.h \ + uint-spbset.h \ + uint-table.h \ url.h \ urlapi-int.h \ urldata.h \ diff --git a/lib/asyn.h b/lib/asyn.h index 39de04320d..a8404bb6e1 100644 --- a/lib/asyn.h +++ b/lib/asyn.h @@ -26,6 +26,9 @@ #include "curl_setup.h" +struct Curl_easy; +struct Curl_dns_entry; + #ifdef CURLRES_ASYNCH #include "curl_addrinfo.h" @@ -33,9 +36,7 @@ struct addrinfo; struct hostent; -struct Curl_easy; struct connectdata; -struct Curl_dns_entry; #if defined(CURLRES_ARES) && defined(CURLRES_THREADED) #error cannot have both CURLRES_ARES and CURLRES_THREADED defined diff --git a/lib/conncache.c b/lib/conncache.c index 072fdd44fa..d2b4dbccc6 100644 --- a/lib/conncache.c +++ b/lib/conncache.c @@ -44,6 +44,7 @@ #include "select.h" #include "strcase.h" #include "strparse.h" +#include "uint-table.h" /* The last 3 #include files should be in this order */ #include "curl_printf.h" @@ -533,7 +534,7 @@ bool Curl_cpool_conn_now_idle(struct Curl_easy *data, struct connectdata *conn) { unsigned int maxconnects = !data->multi->maxconnects ? - data->multi->num_easy * 4 : data->multi->maxconnects; + (Curl_multi_xfers_running(data->multi) * 4) : data->multi->maxconnects; struct connectdata *oldest_idle = NULL; struct cpool *cpool = cpool_get_instance(data); bool kept = TRUE; @@ -619,8 +620,8 @@ static void cpool_discard_conn(struct cpool *cpool, */ if(CONN_INUSE(conn) && !aborted) { CURL_TRC_M(data, "[CPOOL] not discarding #%" FMT_OFF_T - " still in use by %zu transfers", conn->connection_id, - CONN_INUSE(conn)); + " still in use by %u transfers", conn->connection_id, + CONN_ATTACHED(conn)); return; } @@ -664,7 +665,7 @@ void Curl_conn_terminate(struct Curl_easy *data, * are other users of it */ if(CONN_INUSE(conn) && !aborted) { DEBUGASSERT(0); /* does this ever happen? */ - DEBUGF(infof(data, "Curl_disconnect when inuse: %zu", CONN_INUSE(conn))); + DEBUGF(infof(data, "Curl_disconnect when inuse: %u", CONN_ATTACHED(conn))); return; } diff --git a/lib/doh.c b/lib/doh.c index 65506ea323..3f4747a155 100644 --- a/lib/doh.c +++ b/lib/doh.c @@ -287,7 +287,7 @@ static CURLcode doh_probe_run(struct Curl_easy *data, DNStype dnstype, const char *host, const char *url, CURLM *multi, - curl_off_t *pmid) + unsigned int *pmid) { struct Curl_easy *doh = NULL; CURLcode result = CURLE_OK; @@ -295,7 +295,7 @@ static CURLcode doh_probe_run(struct Curl_easy *data, struct doh_request *doh_req; DOHcode d; - *pmid = -1; + *pmid = UINT_MAX; doh_req = calloc(1, sizeof(*doh_req)); if(!doh_req) @@ -490,7 +490,7 @@ struct Curl_addrinfo *Curl_doh(struct Curl_easy *data, return NULL; for(i = 0; i < DOH_SLOT_COUNT; ++i) { - dohp->probe_resp[i].probe_mid = -1; + dohp->probe_resp[i].probe_mid = UINT_MAX; Curl_dyn_init(&dohp->probe_resp[i].body, DYN_DOH_RESPONSE); } @@ -1238,8 +1238,8 @@ CURLcode Curl_doh_is_resolved(struct Curl_easy *data, if(!dohp) return CURLE_OUT_OF_MEMORY; - if(dohp->probe_resp[DOH_SLOT_IPV4].probe_mid < 0 && - dohp->probe_resp[DOH_SLOT_IPV6].probe_mid < 0) { + if(dohp->probe_resp[DOH_SLOT_IPV4].probe_mid == UINT_MAX && + dohp->probe_resp[DOH_SLOT_IPV6].probe_mid == UINT_MAX) { failf(data, "Could not DoH-resolve: %s", dohp->host); return CONN_IS_PROXIED(data->conn) ? CURLE_COULDNT_RESOLVE_PROXY : CURLE_COULDNT_RESOLVE_HOST; @@ -1334,19 +1334,19 @@ void Curl_doh_close(struct Curl_easy *data) struct doh_probes *doh = data->state.async.doh; if(doh && data->multi) { struct Curl_easy *probe_data; - curl_off_t mid; + unsigned int mid; size_t slot; for(slot = 0; slot < DOH_SLOT_COUNT; slot++) { mid = doh->probe_resp[slot].probe_mid; - if(mid < 0) + if(mid == UINT_MAX) continue; - doh->probe_resp[slot].probe_mid = -1; + doh->probe_resp[slot].probe_mid = UINT_MAX; + /* should have been called before data is removed from multi handle */ DEBUGASSERT(data->multi); - probe_data = data->multi ? Curl_multi_get_handle(data->multi, mid) : + probe_data = data->multi ? Curl_multi_get_easy(data->multi, mid) : NULL; if(!probe_data) { - DEBUGF(infof(data, "Curl_doh_close: xfer for mid=%" - FMT_OFF_T " not found!", + DEBUGF(infof(data, "Curl_doh_close: xfer for mid=%u not found!", doh->probe_resp[slot].probe_mid)); continue; } diff --git a/lib/doh.h b/lib/doh.h index ddabac8863..55828767a3 100644 --- a/lib/doh.h +++ b/lib/doh.h @@ -59,6 +59,15 @@ typedef enum { DNS_TYPE_HTTPS = 65 } DNStype; +/* one of these for each DoH request */ +struct doh_probe { + unsigned int easy_mid; /* multi id of easy handle doing the lookup */ + DNStype dnstype; + unsigned char req_body[512]; + size_t req_body_len; + struct dynbuf resp_body; +}; + enum doh_slot_num { /* Explicit values for first two symbols so as to match hard-coded * constants in existing code @@ -85,15 +94,15 @@ enum doh_slot_num { /* each DoH probe request has this * as easy meta for CURL_EZM_DOH_PROBE */ struct doh_request { - DNStype dnstype; - unsigned char req_body[512]; - size_t req_body_len; struct curl_slist *req_hds; struct dynbuf resp_body; + size_t req_body_len; + unsigned char req_body[512]; + DNStype dnstype; }; struct doh_response { - curl_off_t probe_mid; + unsigned int probe_mid; struct dynbuf body; DNStype dnstype; CURLcode result; diff --git a/lib/easy.c b/lib/easy.c index 3f7b3d6744..f63c73c8af 100644 --- a/lib/easy.c +++ b/lib/easy.c @@ -625,21 +625,15 @@ static CURLcode wait_or_timeout(struct Curl_multi *multi, struct events *ev) } else { /* here pollrc is > 0 */ - struct Curl_llist_node *e = Curl_llist_head(&multi->process); - struct Curl_easy *data; - unsigned int i; - DEBUGASSERT(e); - data = Curl_node_elem(e); - DEBUGASSERT(data); - /* loop over the monitored sockets to see which ones had activity */ + unsigned int i; for(i = 0; i < numfds; i++) { if(fds[i].revents) { /* socket activity, tell libcurl */ int act = poll2cselect(fds[i].revents); /* convert */ /* sending infof "randomly" to the first easy handle */ - infof(data, "call curl_multi_socket_action(socket " + infof(multi->admin, "call curl_multi_socket_action(socket " "%" FMT_SOCKET_T ")", (curl_socket_t)fds[i].fd); mcode = curl_multi_socket_action(multi, fds[i].fd, act, &ev->running_handles); @@ -794,7 +788,7 @@ static CURLcode easy_perform(struct Curl_easy *data, bool events) else { /* this multi handle will only ever have a single easy handle attached to it, so make it use minimal hash sizes */ - multi = Curl_multi_handle(1, 3, 7, 3); + multi = Curl_multi_handle(16, 1, 3, 7, 3); if(!multi) return CURLE_OUT_OF_MEMORY; } @@ -981,8 +975,8 @@ CURL *curl_easy_duphandle(CURL *d) outcurl->state.lastconnect_id = -1; outcurl->state.recent_conn_id = -1; outcurl->id = -1; - outcurl->mid = -1; - outcurl->master_mid = -1; + outcurl->mid = UINT_MAX; + outcurl->master_mid = UINT_MAX; #ifndef CURL_DISABLE_HTTP Curl_llist_init(&outcurl->state.httphdrs, NULL); @@ -1136,7 +1130,7 @@ void curl_easy_reset(CURL *d) #if !defined(CURL_DISABLE_HTTP) && !defined(CURL_DISABLE_DIGEST_AUTH) Curl_http_auth_cleanup_digest(data); #endif - data->master_mid = -1; + data->master_mid = UINT_MAX; } /* diff --git a/lib/hash_offt.c b/lib/hash_offt.c index 2edc81af16..cef29742a2 100644 --- a/lib/hash_offt.c +++ b/lib/hash_offt.c @@ -224,14 +224,209 @@ size_t Curl_hash_offt_count(struct Curl_hash_offt *h) return h->size; } -void Curl_hash_offt_visit(struct Curl_hash_offt *h, - Curl_hash_offt_visit_cb *cb, +/* FOR NOW: basically a duplicate of Curl_hash_offt, BUT we hope to + * eliminate the offt variant in the near future. */ + +/* random patterns for API verification */ +#ifdef DEBUGBUILD +#define CURL_UINTHASHINIT 0x7117e779 +#endif + +static unsigned int uint_hash_hash(unsigned int id, unsigned int slots) +{ + return (id % slots); +} + + +struct uint_hash_entry { + struct uint_hash_entry *next; + void *value; + unsigned int id; +}; + +void Curl_uint_hash_init(struct uint_hash *h, + unsigned int slots, + Curl_uint_hash_dtor *dtor) +{ + DEBUGASSERT(h); + DEBUGASSERT(slots); + + h->table = NULL; + h->dtor = dtor; + h->size = 0; + h->slots = slots; +#ifdef DEBUGBUILD + h->init = CURL_UINTHASHINIT; +#endif +} + +static struct uint_hash_entry *uint_hash_mk_entry(unsigned int id, void *value) +{ + struct uint_hash_entry *e; + + /* allocate the struct for the hash entry */ + e = malloc(sizeof(*e)); + if(e) { + e->id = id; + e->next = NULL; + e->value = value; + } + return e; +} + +static void uint_hash_entry_clear(struct uint_hash *h, + struct uint_hash_entry *e) +{ + DEBUGASSERT(h); + DEBUGASSERT(e); + if(e->value) { + if(h->dtor) + h->dtor(e->id, e->value); + e->value = NULL; + } +} + +static void uint_hash_entry_destroy(struct uint_hash *h, + struct uint_hash_entry *e) +{ + uint_hash_entry_clear(h, e); + free(e); +} + +static void uint_hash_entry_unlink(struct uint_hash *h, + struct uint_hash_entry **he_anchor, + struct uint_hash_entry *he) +{ + *he_anchor = he->next; + --h->size; +} + +static void uint_hash_elem_link(struct uint_hash *h, + struct uint_hash_entry **he_anchor, + struct uint_hash_entry *he) +{ + he->next = *he_anchor; + *he_anchor = he; + ++h->size; +} + +#define CURL_UINT_HASH_SLOT(h,id) h->table[uint_hash_hash(id, h->slots)] +#define CURL_UINT_HASH_SLOT_ADDR(h,id) &CURL_HASH_OFFT_SLOT(h,id) + +bool Curl_uint_hash_set(struct uint_hash *h, unsigned int id, void *value) +{ + struct uint_hash_entry *he, **slot; + + DEBUGASSERT(h); + DEBUGASSERT(h->slots); + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + if(!h->table) { + h->table = calloc(h->slots, sizeof(*he)); + if(!h->table) + return FALSE; /* OOM */ + } + + slot = CURL_UINT_HASH_SLOT_ADDR(h, id); + for(he = *slot; he; he = he->next) { + if(he->id == id) { + /* existing key entry, overwrite by clearing old pointer */ + uint_hash_entry_clear(h, he); + he->value = value; + return TRUE; + } + } + + he = uint_hash_mk_entry(id, value); + if(!he) + return FALSE; /* OOM */ + + uint_hash_elem_link(h, slot, he); + return TRUE; +} + +bool Curl_uint_hash_remove(struct uint_hash *h, unsigned int id) +{ + DEBUGASSERT(h); + DEBUGASSERT(h->slots); + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + if(h->table) { + struct uint_hash_entry *he, **he_anchor; + + he_anchor = CURL_UINT_HASH_SLOT_ADDR(h, id); + while(*he_anchor) { + he = *he_anchor; + if(id == he->id) { + uint_hash_entry_unlink(h, he_anchor, he); + uint_hash_entry_destroy(h, he); + return TRUE; + } + he_anchor = &he->next; + } + } + return FALSE; +} + +void *Curl_uint_hash_get(struct uint_hash *h, unsigned int id) +{ + DEBUGASSERT(h); + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + if(h->table) { + struct uint_hash_entry *he; + DEBUGASSERT(h->slots); + he = CURL_UINT_HASH_SLOT(h, id); + while(he) { + if(id == he->id) { + return he->value; + } + he = he->next; + } + } + return NULL; +} + +static void uint_hash_clear(struct uint_hash *h) +{ + if(h && h->table) { + struct uint_hash_entry *he, **he_anchor; + size_t i; + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + for(i = 0; i < h->slots; ++i) { + he_anchor = &h->table[i]; + while(*he_anchor) { + he = *he_anchor; + uint_hash_entry_unlink(h, he_anchor, he); + uint_hash_entry_destroy(h, he); + } + } + } +} + +void +Curl_uint_hash_destroy(struct uint_hash *h) +{ + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + if(h->table) { + uint_hash_clear(h); + Curl_safefree(h->table); + } + DEBUGASSERT(h->size == 0); + h->slots = 0; +} + +unsigned int Curl_uint_hash_count(struct uint_hash *h) +{ + DEBUGASSERT(h->init == CURL_UINTHASHINIT); + return h->size; +} + +void Curl_uint_hash_visit(struct uint_hash *h, + Curl_uint_hash_visit_cb *cb, void *user_data) { if(h && h->table && cb) { - struct Curl_hash_offt_entry *he; + struct uint_hash_entry *he; size_t i; - DEBUGASSERT(h->init == CURL_HASHOFFTINIT); + DEBUGASSERT(h->init == CURL_UINTHASHINIT); for(i = 0; i < h->slots; ++i) { for(he = h->table[i]; he; he = he->next) { if(!cb(he->id, he->value, user_data)) diff --git a/lib/hash_offt.h b/lib/hash_offt.h index 02cbec1ea9..80bab95c2a 100644 --- a/lib/hash_offt.h +++ b/lib/hash_offt.h @@ -56,12 +56,38 @@ void Curl_hash_offt_clear(struct Curl_hash_offt *h); size_t Curl_hash_offt_count(struct Curl_hash_offt *h); -typedef bool Curl_hash_offt_visit_cb(curl_off_t id, void *value, +/* A version with unsigned int as key */ +typedef void Curl_uint_hash_dtor(unsigned int id, void *value); +struct uint_hash_entry; + +/* Hash for `unsigned int` as key */ +struct uint_hash { + struct uint_hash_entry **table; + Curl_uint_hash_dtor *dtor; + unsigned int slots; + unsigned int size; +#ifdef DEBUGBUILD + int init; +#endif +}; + + +void Curl_uint_hash_init(struct uint_hash *h, + unsigned int slots, + Curl_uint_hash_dtor *dtor); +void Curl_uint_hash_destroy(struct uint_hash *h); + +bool Curl_uint_hash_set(struct uint_hash *h, unsigned int id, void *value); +bool Curl_uint_hash_remove(struct uint_hash *h, unsigned int id); +void *Curl_uint_hash_get(struct uint_hash *h, unsigned int id); +unsigned int Curl_uint_hash_count(struct uint_hash *h); + + +typedef bool Curl_uint_hash_visit_cb(unsigned int id, void *value, void *user_data); -void Curl_hash_offt_visit(struct Curl_hash_offt *h, - Curl_hash_offt_visit_cb *cb, +void Curl_uint_hash_visit(struct uint_hash *h, + Curl_uint_hash_visit_cb *cb, void *user_data); - #endif /* HEADER_CURL_HASH_OFFT_H */ diff --git a/lib/http2.c b/lib/http2.c index a1221dcc51..9423a5d2a1 100644 --- a/lib/http2.c +++ b/lib/http2.c @@ -136,7 +136,7 @@ struct cf_h2_ctx { struct bufc_pool stream_bufcp; /* spares for stream buffers */ struct dynbuf scratch; /* scratch buffer for temp use */ - struct Curl_hash_offt streams; /* hash of `data->mid` to `h2_stream_ctx` */ + struct uint_hash streams; /* hash of `data->mid` to `h2_stream_ctx` */ size_t drain_total; /* sum of all stream's UrlState drain */ uint32_t max_concurrent_streams; uint32_t goaway_error; /* goaway error code from server */ @@ -159,7 +159,7 @@ struct cf_h2_ctx { #define CF_CTX_CALL_DATA(cf) \ ((struct cf_h2_ctx *)(cf)->ctx)->call_data -static void h2_stream_hash_free(curl_off_t id, void *stream); +static void h2_stream_hash_free(unsigned int id, void *stream); static void cf_h2_ctx_init(struct cf_h2_ctx *ctx, bool via_h1_upgrade) { @@ -167,7 +167,7 @@ static void cf_h2_ctx_init(struct cf_h2_ctx *ctx, bool via_h1_upgrade) Curl_bufq_initp(&ctx->inbufq, &ctx->stream_bufcp, H2_NW_RECV_CHUNKS, 0); Curl_bufq_initp(&ctx->outbufq, &ctx->stream_bufcp, H2_NW_SEND_CHUNKS, 0); Curl_dyn_init(&ctx->scratch, CURL_MAX_HTTP_HEADER); - Curl_hash_offt_init(&ctx->streams, 63, h2_stream_hash_free); + Curl_uint_hash_init(&ctx->streams, 63, h2_stream_hash_free); ctx->remote_max_sid = 2147483647; ctx->via_h1_upgrade = via_h1_upgrade; #ifdef DEBUGBUILD @@ -192,7 +192,7 @@ static void cf_h2_ctx_free(struct cf_h2_ctx *ctx) Curl_bufq_free(&ctx->outbufq); Curl_bufcp_free(&ctx->stream_bufcp); Curl_dyn_free(&ctx->scratch); - Curl_hash_offt_destroy(&ctx->streams); + Curl_uint_hash_destroy(&ctx->streams); memset(ctx, 0, sizeof(*ctx)); } free(ctx); @@ -238,7 +238,7 @@ struct h2_stream_ctx { }; #define H2_STREAM_CTX(ctx,data) ((struct h2_stream_ctx *)(\ - data? Curl_hash_offt_get(&(ctx)->streams, (data)->mid) : NULL)) + data? Curl_uint_hash_get(&(ctx)->streams, (data)->mid) : NULL)) static struct h2_stream_ctx *h2_stream_ctx_create(struct cf_h2_ctx *ctx) { @@ -282,7 +282,7 @@ static void h2_stream_ctx_free(struct h2_stream_ctx *stream) free(stream); } -static void h2_stream_hash_free(curl_off_t id, void *stream) +static void h2_stream_hash_free(unsigned int id, void *stream) { (void)id; DEBUGASSERT(stream); @@ -414,7 +414,7 @@ static CURLcode http2_data_setup(struct Curl_cfilter *cf, if(!stream) return CURLE_OUT_OF_MEMORY; - if(!Curl_hash_offt_set(&ctx->streams, data->mid, stream)) { + if(!Curl_uint_hash_set(&ctx->streams, data->mid, stream)) { h2_stream_ctx_free(stream); return CURLE_OUT_OF_MEMORY; } @@ -452,7 +452,7 @@ static void http2_data_done(struct Curl_cfilter *cf, struct Curl_easy *data) nghttp2_session_send(ctx->h2); } - Curl_hash_offt_remove(&ctx->streams, data->mid); + Curl_uint_hash_remove(&ctx->streams, data->mid); } static int h2_client_new(struct Curl_cfilter *cf, @@ -1061,8 +1061,8 @@ static int push_promise(struct Curl_cfilter *cf, newhandle->req.maxdownload = -1; newhandle->req.size = -1; - CURL_TRC_CF(data, cf, "promise easy handle added to multi, mid=%" - FMT_OFF_T, newhandle->mid); + CURL_TRC_CF(data, cf, "promise easy handle added to multi, mid=%u", + newhandle->mid); rv = nghttp2_session_set_stream_user_data(ctx->h2, newstream->id, newhandle); @@ -2154,7 +2154,7 @@ static ssize_t cf_h2_recv(struct Curl_cfilter *cf, struct Curl_easy *data, * a read() is called anyway. It is not clear what the calling sequence * is for such a case. */ failf(data, "http/2 recv on a transfer never opened " - "or already cleared, mid=%" FMT_OFF_T, data->mid); + "or already cleared, mid=%u", data->mid); *err = CURLE_HTTP2; return -1; } @@ -2806,7 +2806,7 @@ static CURLcode cf_h2_query(struct Curl_cfilter *cf, CF_DATA_SAVE(save, cf, data); if(nghttp2_session_check_request_allowed(ctx->h2) == 0) { /* the limit is what we have in use right now */ - effective_max = CONN_INUSE(cf->conn); + effective_max = CONN_ATTACHED(cf->conn); } else { effective_max = ctx->max_concurrent_streams; diff --git a/lib/multi.c b/lib/multi.c index 6afcf7a895..d2615d3b4c 100644 --- a/lib/multi.c +++ b/lib/multi.c @@ -58,6 +58,9 @@ #include "curl_memory.h" #include "memdebug.h" +/* initial multi->xfers table size for a full multi */ +#define CURL_XFER_TABLE_SIZE 512 + /* CURL_SOCKET_HASH_TABLE_SIZE should be a prime number. Increasing it from 97 to 911 takes on a 32-bit machine 4 x 804 = 3211 more bytes. Still, every @@ -103,6 +106,9 @@ static CURLMcode multi_timeout(struct Curl_multi *multi, long *timeout_ms); static void process_pending_handles(struct Curl_multi *multi); static void multi_xfer_bufs_free(struct Curl_multi *multi); +#ifdef DEBUGBUILD +static void multi_xfer_tbl_dump(struct Curl_multi *multi); +#endif /* function pointer called once when switching TO a state */ typedef void (*init_multistate_func)(struct Curl_easy *data); @@ -166,10 +172,12 @@ static void mstate(struct Curl_easy *data, CURLMstate state data->mstate = state; if(state == MSTATE_COMPLETED) { - /* changing to COMPLETED means there is one less easy handle 'alive' */ - DEBUGASSERT(data->multi->num_alive > 0); - data->multi->num_alive--; - if(!data->multi->num_alive) { + /* changing to COMPLETED means it is in process and needs to go */ + DEBUGASSERT(Curl_uint_bset_contains(&data->multi->process, data->mid)); + Curl_uint_bset_remove(&data->multi->process, data->mid); + Curl_uint_bset_remove(&data->multi->pending, data->mid); /* to be sure */ + + if(Curl_uint_bset_empty(&data->multi->process)) { /* free the transfer buffer when we have no more active transfers */ multi_xfer_bufs_free(data->multi); } @@ -209,7 +217,8 @@ static void multi_addmsg(struct Curl_multi *multi, struct Curl_message *msg) Curl_llist_append(&multi->msglist, msg, &msg->list); } -struct Curl_multi *Curl_multi_handle(size_t ev_hashsize, /* event hash */ +struct Curl_multi *Curl_multi_handle(unsigned int xfer_table_size, + size_t ev_hashsize, /* event hash */ size_t chashsize, /* connection hash */ size_t dnssize, /* dns hash */ size_t sesssize) /* TLS session cache */ @@ -223,9 +232,23 @@ struct Curl_multi *Curl_multi_handle(size_t ev_hashsize, /* event hash */ Curl_dnscache_init(&multi->dnscache, dnssize); Curl_multi_ev_init(multi, ev_hashsize); - + Curl_uint_tbl_init(&multi->xfers, NULL); + Curl_uint_bset_init(&multi->process); + Curl_uint_bset_init(&multi->pending); + Curl_uint_bset_init(&multi->msgsent); Curl_hash_init(&multi->proto_hash, 23, Curl_hash_str, Curl_str_key_compare, ph_freeentry); + Curl_llist_init(&multi->msglist, NULL); + + multi->multiplexing = TRUE; + multi->max_concurrent_streams = 100; + multi->last_timeout_ms = -1; + + if(Curl_uint_bset_resize(&multi->process, xfer_table_size) || + Curl_uint_bset_resize(&multi->pending, xfer_table_size) || + Curl_uint_bset_resize(&multi->msgsent, xfer_table_size) || + Curl_uint_tbl_resize(&multi->xfers, xfer_table_size)) + goto error; multi->admin = curl_easy_init(); if(!multi->admin) @@ -238,6 +261,7 @@ struct Curl_multi *Curl_multi_handle(size_t ev_hashsize, /* event hash */ if(getenv("CURL_DEBUG")) multi->admin->set.verbose = TRUE; #endif + Curl_uint_tbl_add(&multi->xfers, multi->admin, &multi->admin->mid); if(Curl_cshutdn_init(&multi->cshutdn, multi)) goto error; @@ -247,15 +271,6 @@ struct Curl_multi *Curl_multi_handle(size_t ev_hashsize, /* event hash */ if(Curl_ssl_scache_create(sesssize, 2, &multi->ssl_scache)) goto error; - Curl_llist_init(&multi->msglist, NULL); - Curl_llist_init(&multi->process, NULL); - Curl_llist_init(&multi->pending, NULL); - Curl_llist_init(&multi->msgsent, NULL); - - multi->multiplexing = TRUE; - multi->max_concurrent_streams = 100; - multi->last_timeout_ms = -1; - #ifdef USE_WINSOCK multi->wsa_event = WSACreateEvent(); if(multi->wsa_event == WSA_INVALID_EVENT) @@ -284,13 +299,19 @@ error: Curl_close(&multi->admin); } + Curl_uint_bset_destroy(&multi->process); + Curl_uint_bset_destroy(&multi->pending); + Curl_uint_bset_destroy(&multi->msgsent); + Curl_uint_tbl_destroy(&multi->xfers); + free(multi); return NULL; } CURLM *curl_multi_init(void) { - return Curl_multi_handle(CURL_SOCKET_HASH_TABLE_SIZE, + return Curl_multi_handle(CURL_XFER_TABLE_SIZE, + CURL_SOCKET_HASH_TABLE_SIZE, CURL_CONNECTION_HASH_SIZE, CURL_DNS_HASH_SIZE, CURL_TLS_SESSION_SIZE); @@ -310,6 +331,43 @@ static void multi_warn_debug(struct Curl_multi *multi, struct Curl_easy *data) #define multi_warn_debug(x,y) Curl_nop_stmt #endif + +static CURLMcode multi_xfers_add(struct Curl_multi *multi, + struct Curl_easy *data) +{ + /* We want `multi->xfers` to have "sufficient" free rows, so that we do + * have to reuse the `mid` from a just removed easy right away. + * Since uint_tbl and uint_bset is quite memory efficient, + * regard less than 25% free as insufficient. + * (for low capacities, e.g. multi_easy, 4 or less). */ + unsigned int capacity = Curl_uint_tbl_capacity(&multi->xfers); + unsigned int unused = capacity - Curl_uint_tbl_count(&multi->xfers); + unsigned int min_unused = CURLMAX(capacity >> 2, 4); + + if(unused <= min_unused) { + /* make it a 64 multiple, since our bitsets frow by that and + * small (easy_multi) grows to at least 64 on first resize. */ + unsigned int newsize = ((capacity + min_unused) + 63) / 64; + /* Grow the bitsets first. Should one fail, we do not need + * to downsize the already resized ones. The sets continue + * to work properly when larger than the table, but not + * the other way around. */ + if(Curl_uint_bset_resize(&multi->process, newsize) || + Curl_uint_bset_resize(&multi->pending, newsize) || + Curl_uint_bset_resize(&multi->msgsent, newsize) || + Curl_uint_tbl_resize(&multi->xfers, newsize)) + return CURLM_OUT_OF_MEMORY; + CURL_TRC_M(data, "increased xfer table size to %u", newsize); + } + /* Insert the easy into the table now that MUST have room for it */ + if(!Curl_uint_tbl_add(&multi->xfers, data, &data->mid)) { + DEBUGASSERT(0); + return CURLM_OUT_OF_MEMORY; + } + return CURLM_OK; +} + + CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) { CURLMcode rc; @@ -334,10 +392,15 @@ CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) if(multi->dead) { /* a "dead" handle cannot get added transfers while any existing easy handles are still alive - but if there are none alive anymore, it is - fine to start over and unmark the "deadness" of this handle */ - if(multi->num_alive) + fine to start over and unmark the "deadness" of this handle. + This means only the admin handle MUST be present. */ + if((Curl_uint_tbl_count(&multi->xfers) != 1) || + !Curl_uint_tbl_contains(&multi->xfers, 0)) return CURLM_ABORTED_BY_CALLBACK; multi->dead = FALSE; + Curl_uint_bset_clear(&multi->process); + Curl_uint_bset_clear(&multi->pending); + Curl_uint_bset_clear(&multi->msgsent); } if(data->multi_easy) { @@ -347,6 +410,10 @@ CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) data->multi_easy = NULL; } + /* Insert the easy into the multi->xfers table, assigning it a `mid`. */ + if(multi_xfers_add(multi, data)) + return CURLM_OUT_OF_MEMORY; + /* Initialize timeout list for this handle */ Curl_llist_init(&data->state.timeoutlist, NULL); @@ -376,6 +443,8 @@ CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) rc = Curl_update_timer(multi); if(rc) { data->multi = NULL; /* not anymore */ + Curl_uint_tbl_remove(&multi->xfers, data->mid); + data->mid = UINT_MAX; return rc; } @@ -390,19 +459,9 @@ CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) data->psl = &multi->psl; #endif - /* add the easy handle to the process list */ - Curl_llist_append(&multi->process, data, &data->multi_queue); - - /* increase the node-counter */ - multi->num_easy++; - - /* increase the alive-counter */ - multi->num_alive++; - - /* the identifier inside the multi instance */ - data->mid = multi->next_easy_mid++; - if(multi->next_easy_mid <= 0) - multi->next_easy_mid = 0; + /* add the easy handle to the process set */ + Curl_uint_bset_add(&multi->process, data->mid); + ++multi->xfers_alive; Curl_cpool_xfer_init(data); multi_warn_debug(multi, data); @@ -416,7 +475,9 @@ CURLMcode curl_multi_add_handle(CURLM *m, CURL *d) data->set.server_response_timeout; multi->admin->set.no_signal = data->set.no_signal; - CURL_TRC_M(data, "added, transfers=%u", multi->num_easy); + CURL_TRC_M(data, "added to multi, mid=%u, running=%u, total=%u", + data->mid, Curl_multi_xfers_running(multi), + Curl_uint_tbl_count(&multi->xfers)); return CURLM_OK; } @@ -448,10 +509,12 @@ static void multi_done_locked(struct connectdata *conn, Curl_detach_connection(data); + CURL_TRC_M(data, "multi_done_locked, in use=%u", + Curl_uint_spbset_count(&conn->xfers_attached)); if(CONN_INUSE(conn)) { /* Stop if still used. */ - CURL_TRC_M(data, "Connection still in use %zu, no more multi_done now!", - Curl_llist_count(&conn->easyq)); + CURL_TRC_M(data, "Connection still in use %u, no more multi_done now!", + Curl_uint_spbset_count(&conn->xfers_attached)); return; } @@ -614,6 +677,7 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) struct Curl_llist_node *e; CURLMcode rc; bool removed_timer = FALSE; + unsigned int mid; /* First, make some basic checks that the CURLM handle is a good handle */ if(!GOOD_MULTI_HANDLE(multi)) @@ -631,7 +695,11 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) if(data->multi != multi) return CURLM_BAD_EASY_HANDLE; - if(!multi->num_easy) { + if(data->mid == UINT_MAX) { + DEBUGASSERT(0); + return CURLM_INTERNAL_ERROR; + } + if(Curl_uint_tbl_get(&multi->xfers, data->mid) != data) { DEBUGASSERT(0); return CURLM_INTERNAL_ERROR; } @@ -643,12 +711,6 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) /* If the 'state' is not INIT or COMPLETED, we might need to do something nice to put the easy_handle in a good known state when this returns. */ - if(premature) { - /* this handle is "alive" so we need to count down the total number of - alive connections when this is removed */ - multi->num_alive--; - } - if(data->conn && data->mstate > MSTATE_DO && data->mstate < MSTATE_COMPLETED) { @@ -671,8 +733,9 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) called. Do it after multi_done() in case that sets another time! */ removed_timer = Curl_expire_clear(data); - /* the handle is in a list, remove it from whichever it is */ - Curl_node_remove(&data->multi_queue); + /* If in `msgsent`, it was deducted from `multi->xfers_alive` already. */ + if(!Curl_uint_bset_contains(&multi->msgsent, data->mid)) + --multi->xfers_alive; Curl_wildcard_dtor(&data->wildcard); @@ -725,13 +788,19 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) } } - data->multi = NULL; /* clear the association to this multi handle */ - data->mid = -1; - data->master_mid = -1; + /* clear the association to this multi handle */ + mid = data->mid; + DEBUGASSERT(Curl_uint_tbl_contains(&multi->xfers, mid)); + Curl_uint_tbl_remove(&multi->xfers, mid); + Curl_uint_bset_remove(&multi->process, mid); + Curl_uint_bset_remove(&multi->pending, mid); + Curl_uint_bset_remove(&multi->msgsent, mid); + data->multi = NULL; + data->mid = UINT_MAX; + data->master_mid = UINT_MAX; /* NOTE NOTE NOTE We do not touch the easy handle here! */ - multi->num_easy--; /* one less to care about now */ process_pending_handles(multi); if(removed_timer) { @@ -740,7 +809,9 @@ CURLMcode curl_multi_remove_handle(CURLM *m, CURL *d) return rc; } - CURL_TRC_M(data, "removed, transfers=%u", multi->num_easy); + CURL_TRC_M(data, "removed from multi, mid=%u, running=%u, total=%u", + mid, Curl_multi_xfers_running(multi), + Curl_uint_tbl_count(&multi->xfers)); return CURLM_OK; } @@ -760,7 +831,7 @@ void Curl_detach_connection(struct Curl_easy *data) { struct connectdata *conn = data->conn; if(conn) { - Curl_node_remove(&data->conn_queue); + Curl_uint_spbset_remove(&conn->xfers_attached, data->mid); } data->conn = NULL; } @@ -777,7 +848,7 @@ void Curl_attach_connection(struct Curl_easy *data, DEBUGASSERT(!data->conn); DEBUGASSERT(conn); data->conn = conn; - Curl_llist_append(&conn->easyq, data, &data->conn_queue); + Curl_uint_spbset_add(&conn->xfers_attached, data->mid); if(conn->handler && conn->handler->attach) conn->handler->attach(data, conn); } @@ -1009,9 +1080,8 @@ CURLMcode curl_multi_fdset(CURLM *m, Some easy handles may not have connected to the remote host yet, and then we must make sure that is done. */ int this_max_fd = -1; - struct Curl_llist_node *e; struct Curl_multi *multi = m; - unsigned int i; + unsigned int i, mid; (void)exc_fd_set; /* not used */ if(!GOOD_MULTI_HANDLE(multi)) @@ -1020,30 +1090,37 @@ CURLMcode curl_multi_fdset(CURLM *m, if(multi->in_callback) return CURLM_RECURSIVE_API_CALL; - for(e = Curl_llist_head(&multi->process); e; e = Curl_node_next(e)) { - struct Curl_easy *data = Curl_node_elem(e); - struct easy_pollset ps; - - Curl_multi_getsock(data, &ps, "curl_multi_fdset"); + if(Curl_uint_bset_first(&multi->process, &mid)) { + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + struct easy_pollset ps; - for(i = 0; i < ps.num; i++) { - if(!FDSET_SOCK(ps.sockets[i])) - /* pretend it does not exist */ + if(!data) { + DEBUGASSERT(0); continue; + } + + Curl_multi_getsock(data, &ps, "curl_multi_fdset"); + for(i = 0; i < ps.num; i++) { + if(!FDSET_SOCK(ps.sockets[i])) + /* pretend it does not exist */ + continue; #if defined(__DJGPP__) #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Warith-conversion" #endif - if(ps.actions[i] & CURL_POLL_IN) - FD_SET(ps.sockets[i], read_fd_set); - if(ps.actions[i] & CURL_POLL_OUT) - FD_SET(ps.sockets[i], write_fd_set); + if(ps.actions[i] & CURL_POLL_IN) + FD_SET(ps.sockets[i], read_fd_set); + if(ps.actions[i] & CURL_POLL_OUT) + FD_SET(ps.sockets[i], write_fd_set); #if defined(__DJGPP__) #pragma GCC diagnostic pop #endif - if((int)ps.sockets[i] > this_max_fd) - this_max_fd = (int)ps.sockets[i]; + if((int)ps.sockets[i] > this_max_fd) + this_max_fd = (int)ps.sockets[i]; + } } + while(Curl_uint_bset_next(&multi->process, mid, &mid)); } Curl_cshutdn_setfds(&multi->cshutdn, multi->admin, @@ -1061,9 +1138,8 @@ CURLMcode curl_multi_waitfds(CURLM *m, { struct Curl_waitfds cwfds; CURLMcode result = CURLM_OK; - struct Curl_llist_node *e; struct Curl_multi *multi = m; - unsigned int need = 0; + unsigned int need = 0, mid; if(!ufds && (size || !fd_count)) return CURLM_BAD_FUNCTION_ARGUMENT; @@ -1075,12 +1151,19 @@ CURLMcode curl_multi_waitfds(CURLM *m, return CURLM_RECURSIVE_API_CALL; Curl_waitfds_init(&cwfds, ufds, size); - for(e = Curl_llist_head(&multi->process); e; e = Curl_node_next(e)) { - struct Curl_easy *data = Curl_node_elem(e); - struct easy_pollset ps; - - Curl_multi_getsock(data, &ps, "curl_multi_waitfds"); - need += Curl_waitfds_add_ps(&cwfds, &ps); + if(Curl_uint_bset_first(&multi->process, &mid)) { + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + struct easy_pollset ps; + if(!data) { + DEBUGASSERT(0); + Curl_uint_bset_remove(&multi->process, mid); + continue; + } + Curl_multi_getsock(data, &ps, "curl_multi_waitfds"); + need += Curl_waitfds_add_ps(&cwfds, &ps); + } + while(Curl_uint_bset_next(&multi->process, mid, &mid)); } need += Curl_cshutdn_add_waitfds(&multi->cshutdn, multi->admin, &cwfds); @@ -1128,7 +1211,7 @@ static CURLMcode multi_wait(struct Curl_multi *multi, struct curl_pollfds cpfds; unsigned int curl_nfds = 0; /* how many pfds are for curl transfers */ CURLMcode result = CURLM_OK; - struct Curl_llist_node *e; + unsigned int mid; #ifdef USE_WINSOCK WSANETWORKEVENTS wsa_events; @@ -1150,15 +1233,22 @@ static CURLMcode multi_wait(struct Curl_multi *multi, Curl_pollfds_init(&cpfds, a_few_on_stack, NUM_POLLS_ON_STACK); /* Add the curl handles to our pollfds first */ - for(e = Curl_llist_head(&multi->process); e; e = Curl_node_next(e)) { - struct Curl_easy *data = Curl_node_elem(e); - struct easy_pollset ps; - - Curl_multi_getsock(data, &ps, "multi_wait"); - if(Curl_pollfds_add_ps(&cpfds, &ps)) { - result = CURLM_OUT_OF_MEMORY; - goto out; + if(Curl_uint_bset_first(&multi->process, &mid)) { + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + struct easy_pollset ps; + if(!data) { + DEBUGASSERT(0); + Curl_uint_bset_remove(&multi->process, mid); + continue; + } + Curl_multi_getsock(data, &ps, "multi_wait"); + if(Curl_pollfds_add_ps(&cpfds, &ps)) { + result = CURLM_OUT_OF_MEMORY; + goto out; + } } + while(Curl_uint_bset_next(&multi->process, mid, &mid)); } if(Curl_cshutdn_add_pollfds(&multi->cshutdn, multi->admin, &cpfds)) { @@ -2110,10 +2200,9 @@ static CURLMcode state_connect(struct Curl_multi *multi, /* There was no connection available. We will go to the pending state and wait for an available connection. */ multistate(data, MSTATE_PENDING); - /* unlink from process list */ - Curl_node_remove(&data->multi_queue); - /* add handle to pending list */ - Curl_llist_append(&multi->pending, data, &data->multi_queue); + /* move from process to pending set */ + Curl_uint_bset_remove(&multi->process, data->mid); + Curl_uint_bset_add(&multi->pending, data->mid); *resultp = CURLE_OK; return rc; } @@ -2508,23 +2597,21 @@ statemachine_end: } if(MSTATE_COMPLETED == data->mstate) { - if(data->master_mid >= 0) { + if(data->master_mid != UINT_MAX) { /* A sub transfer, not for msgsent to application */ struct Curl_easy *mdata; - CURL_TRC_M(data, "sub xfer done for master %" FMT_OFF_T, - data->master_mid); - mdata = Curl_multi_get_handle(multi, data->master_mid); + CURL_TRC_M(data, "sub xfer done for master %u", data->master_mid); + mdata = Curl_multi_get_easy(multi, data->master_mid); if(mdata) { if(mdata->sub_xfer_done) mdata->sub_xfer_done(mdata, data, result); else - CURL_TRC_M(data, "master easy %" FMT_OFF_T - " without sub_xfer_done.", data->master_mid); + CURL_TRC_M(data, "master easy %u without sub_xfer_done callback.", + data->master_mid); } else { - CURL_TRC_M(data, "master easy %" FMT_OFF_T " already gone.", - data->master_mid); + CURL_TRC_M(data, "master easy %u already gone.", data->master_mid); } } else { @@ -2540,10 +2627,11 @@ statemachine_end: } multistate(data, MSTATE_MSGSENT); - /* unlink from the process list */ - Curl_node_remove(&data->multi_queue); - /* add this handle msgsent list */ - Curl_llist_append(&multi->msgsent, data, &data->multi_queue); + /* remove from the other sets, add to msgsent */ + Curl_uint_bset_remove(&multi->process, data->mid); + Curl_uint_bset_remove(&multi->pending, data->mid); + Curl_uint_bset_add(&multi->msgsent, data->mid); + --multi->xfers_alive; return CURLM_OK; } } while((rc == CURLM_CALL_MULTI_PERFORM) || multi_ischanged(multi, FALSE)); @@ -2558,10 +2646,8 @@ CURLMcode curl_multi_perform(CURLM *m, int *running_handles) CURLMcode returncode = CURLM_OK; struct Curl_tree *t = NULL; struct curltime now = Curl_now(); - struct Curl_llist_node *e; - struct Curl_llist_node *n = NULL; struct Curl_multi *multi = m; - bool first = TRUE; + unsigned int mid; SIGPIPE_VARIABLE(pipe_st); if(!GOOD_MULTI_HANDLE(multi)) @@ -2571,34 +2657,26 @@ CURLMcode curl_multi_perform(CURLM *m, int *running_handles) return CURLM_RECURSIVE_API_CALL; sigpipe_init(&pipe_st); - for(e = Curl_llist_head(&multi->process); e; e = n) { - struct Curl_easy *data = Curl_node_elem(e); - CURLMcode result; - unsigned int num_alive = multi->num_alive; - /* Do the loop and only alter the signal ignore state if the next handle - has a different NO_SIGNAL state than the previous */ - if(first) { - CURL_TRC_M(data, "multi_perform(running=%u)", multi->num_alive); - first = FALSE; - } - - /* the current node might be unlinked in multi_runsingle(), get the next - pointer now */ - n = Curl_node_next(e); - - if(data && data != multi->admin) { - /* connection pool handle is processed below */ - sigpipe_apply(data, &pipe_st); - result = multi_runsingle(multi, &now, data); - if(result) - returncode = result; + if(Curl_uint_bset_first(&multi->process, &mid)) { + CURL_TRC_M(multi->admin, "multi_perform(running=%u)", + Curl_multi_xfers_running(multi)); + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + CURLMcode result; + if(!data) { + DEBUGASSERT(0); + Curl_uint_bset_remove(&multi->process, mid); + continue; + } + if(data != multi->admin) { + /* admin handle is processed below */ + sigpipe_apply(data, &pipe_st); + result = multi_runsingle(multi, &now, data); + if(result) + returncode = result; + } } - if(num_alive != multi->num_alive) - /* Since more than one handle can be removed in a single call to - multi_runsingle(), we cannot easily continue on the next node when a - node has been removed since that node might ALSO have been - removed. */ - n = Curl_llist_head(&multi->process); + while(Curl_uint_bset_next(&multi->process, mid, &mid)); } sigpipe_apply(multi->admin, &pipe_st); @@ -2635,8 +2713,10 @@ CURLMcode curl_multi_perform(CURLM *m, int *running_handles) } } while(t); - if(running_handles) - *running_handles = (int)multi->num_alive; + if(running_handles) { + unsigned int running = Curl_multi_xfers_running(multi); + *running_handles = (running < INT_MAX) ? (int)running : INT_MAX; + } if(CURLM_OK >= returncode) returncode = Curl_update_timer(multi); @@ -2644,63 +2724,58 @@ CURLMcode curl_multi_perform(CURLM *m, int *running_handles) return returncode; } -/* unlink_all_msgsent_handles() moves all nodes back from the msgsent list to - the process list */ -static void unlink_all_msgsent_handles(struct Curl_multi *multi) -{ - struct Curl_llist_node *e; - struct Curl_llist_node *n; - for(e = Curl_llist_head(&multi->msgsent); e; e = n) { - struct Curl_easy *data = Curl_node_elem(e); - n = Curl_node_next(e); - if(data) { - DEBUGASSERT(data->mstate == MSTATE_MSGSENT); - Curl_node_remove(&data->multi_queue); - /* put it into the process list */ - Curl_llist_append(&multi->process, data, &data->multi_queue); - } - } -} - CURLMcode curl_multi_cleanup(CURLM *m) { struct Curl_multi *multi = m; if(GOOD_MULTI_HANDLE(multi)) { - struct Curl_llist_node *e; - struct Curl_llist_node *n; + void *entry; + unsigned int mid; if(multi->in_callback) return CURLM_RECURSIVE_API_CALL; - /* move the pending and msgsent entries back to process - so that there is just one list to iterate over */ - unlink_all_msgsent_handles(multi); - process_pending_handles(multi); + /* First remove all remaining easy handles, + * close internal ones. admin handle is special */ + if(Curl_uint_tbl_first(&multi->xfers, &mid, &entry)) { + do { + struct Curl_easy *data = entry; + if(!GOOD_EASY_HANDLE(data)) + return CURLM_BAD_HANDLE; - /* First remove all remaining easy handles */ - for(e = Curl_llist_head(&multi->process); e; e = n) { - struct Curl_easy *data = Curl_node_elem(e); +#ifdef DEBUGBUILD + if(mid != data->mid) { + CURL_TRC_M(data, "multi_cleanup: still present with mid=%u, " + "but unexpected data->mid=%u\n", mid, data->mid); + DEBUGASSERT(0); + } +#endif - if(!GOOD_EASY_HANDLE(data)) - return CURLM_BAD_HANDLE; + if(data == multi->admin) + continue; - n = Curl_node_next(e); - if(!data->state.done && data->conn) - /* if DONE was never called for this handle */ - (void)multi_done(data, CURLE_OK, TRUE); + if(!data->state.done && data->conn) + /* if DONE was never called for this handle */ + (void)multi_done(data, CURLE_OK, TRUE); - data->multi = NULL; /* clear the association */ + data->multi = NULL; /* clear the association */ + Curl_uint_tbl_remove(&multi->xfers, mid); + data->mid = UINT_MAX; #ifdef USE_LIBPSL - if(data->psl == &multi->psl) - data->psl = NULL; + if(data->psl == &multi->psl) + data->psl = NULL; #endif - if(data->state.internal) - Curl_close(&data); + if(data->state.internal) + Curl_close(&data); + } + while(Curl_uint_tbl_next(&multi->xfers, mid, &mid, &entry)); } + Curl_cpool_destroy(&multi->cpool); Curl_cshutdn_destroy(&multi->cshutdn, multi->admin); if(multi->admin) { + CURL_TRC_M(multi->admin, "multi_cleanup, closing admin handle, done"); multi->admin->multi = NULL; + Curl_uint_tbl_remove(&multi->xfers, multi->admin->mid); Curl_close(&multi->admin); } @@ -2724,6 +2799,16 @@ CURLMcode curl_multi_cleanup(CURLM *m) #endif multi_xfer_bufs_free(multi); +#ifdef DEBUGBUILD + if(Curl_uint_tbl_count(&multi->xfers)) { + multi_xfer_tbl_dump(multi); + DEBUGASSERT(0); + } +#endif + Curl_uint_bset_destroy(&multi->process); + Curl_uint_bset_destroy(&multi->pending); + Curl_uint_bset_destroy(&multi->msgsent); + Curl_uint_tbl_destroy(&multi->xfers); free(multi); return CURLM_OK; @@ -2909,7 +2994,7 @@ static CURLMcode multi_socket(struct Curl_multi *multi, if(result != CURLM_BAD_HANDLE) { /* Reassess event status of all active transfers */ - result = Curl_multi_ev_assess_xfer_list(multi, &multi->process); + result = Curl_multi_ev_assess_xfer_bset(multi, &multi->process); } mrc.run_cpool = TRUE; goto out; @@ -2952,8 +3037,10 @@ out: if(multi_ischanged(multi, TRUE)) process_pending_handles(multi); - if(running_handles) - *running_handles = (int)multi->num_alive; + if(running_handles) { + unsigned int running = Curl_multi_xfers_running(multi); + *running_handles = (running < INT_MAX) ? (int)running : INT_MAX; + } if(CURLM_OK >= result) result = Curl_update_timer(multi); @@ -3403,11 +3490,9 @@ static void move_pending_to_connect(struct Curl_multi *multi, { DEBUGASSERT(data->mstate == MSTATE_PENDING); - /* Remove this node from the pending list */ - Curl_node_remove(&data->multi_queue); - - /* put it into the process list */ - Curl_llist_append(&multi->process, data, &data->multi_queue); + /* Remove this node from the pending set, add into process set */ + Curl_uint_bset_remove(&multi->pending, data->mid); + Curl_uint_bset_add(&multi->process, data->mid); multistate(data, MSTATE_CONNECT); @@ -3431,10 +3516,15 @@ static void move_pending_to_connect(struct Curl_multi *multi, */ static void process_pending_handles(struct Curl_multi *multi) { - struct Curl_llist_node *e = Curl_llist_head(&multi->pending); - if(e) { - struct Curl_easy *data = Curl_node_elem(e); - move_pending_to_connect(multi, data); + unsigned int mid; + if(Curl_uint_bset_first(&multi->pending, &mid)) { + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + DEBUGASSERT(data); + if(data) + move_pending_to_connect(multi, data); + } + while(Curl_uint_bset_next(&multi->pending, mid, &mid)); } } @@ -3458,15 +3548,20 @@ unsigned int Curl_multi_max_concurrent_streams(struct Curl_multi *multi) CURL **curl_multi_get_handles(CURLM *m) { struct Curl_multi *multi = m; - CURL **a = malloc(sizeof(struct Curl_easy *) * (multi->num_easy + 1)); + void *entry; + unsigned int count = Curl_uint_tbl_count(&multi->xfers); + CURL **a = malloc(sizeof(struct Curl_easy *) * (count + 1)); if(a) { - unsigned int i = 0; - struct Curl_llist_node *e; - for(e = Curl_llist_head(&multi->process); e; e = Curl_node_next(e)) { - struct Curl_easy *data = Curl_node_elem(e); - DEBUGASSERT(i < multi->num_easy); - if(!data->state.internal) - a[i++] = data; + unsigned int i = 0, mid; + + if(Curl_uint_tbl_first(&multi->xfers, &mid, &entry)) { + do { + struct Curl_easy *data = entry; + DEBUGASSERT(i < count); + if(!data->state.internal) + a[i++] = data; + } + while(Curl_uint_tbl_next(&multi->xfers, mid, &mid, &entry)); } a[i] = NULL; /* last entry is a NULL */ } @@ -3638,31 +3733,53 @@ static void multi_xfer_bufs_free(struct Curl_multi *multi) multi->xfer_sockbuf_borrowed = FALSE; } -struct Curl_easy *Curl_multi_get_handle(struct Curl_multi *multi, - curl_off_t mid) +struct Curl_easy *Curl_multi_get_easy(struct Curl_multi *multi, + unsigned int mid) { + struct Curl_easy *data = mid ? Curl_uint_tbl_get(&multi->xfers, mid) : NULL; + if(data && GOOD_EASY_HANDLE(data)) + return data; + CURL_TRC_M(multi->admin, "invalid easy handle in xfer table for mid=%u", + mid); + Curl_uint_tbl_remove(&multi->xfers, mid); + return NULL; +} - if(mid >= 0) { - struct Curl_easy *data; - struct Curl_llist_node *e; +unsigned int Curl_multi_xfers_running(struct Curl_multi *multi) +{ + return multi->xfers_alive; +} - for(e = Curl_llist_head(&multi->process); e; e = Curl_node_next(e)) { - data = Curl_node_elem(e); - if(data->mid == mid) - return data; - } - /* may be in msgsent queue */ - for(e = Curl_llist_head(&multi->msgsent); e; e = Curl_node_next(e)) { - data = Curl_node_elem(e); - if(data->mid == mid) - return data; - } - /* may be in pending queue */ - for(e = Curl_llist_head(&multi->pending); e; e = Curl_node_next(e)) { - data = Curl_node_elem(e); - if(data->mid == mid) - return data; - } +#ifdef DEBUGBUILD +static void multi_xfer_dump(struct Curl_multi *multi, unsigned int mid, + void *entry) +{ + struct Curl_easy *data = entry; + + (void)multi; + if(!data) { + fprintf(stderr, "mid=%u, entry=NULL, bug in xfer table?\n", mid); } - return NULL; + else { + fprintf(stderr, "mid=%u, magic=%s, p=%p, id=%" FMT_OFF_T ", url=%s\n", + mid, (data->magic == CURLEASY_MAGIC_NUMBER) ? "GOOD" : "BAD!", + (void *)data, data->id, data->state.url); + } +} + +static void multi_xfer_tbl_dump(struct Curl_multi *multi) +{ + unsigned int mid; + void *entry; + fprintf(stderr, "=== multi xfer table (count=%u, capacity=%u\n", + Curl_uint_tbl_count(&multi->xfers), + Curl_uint_tbl_capacity(&multi->xfers)); + if(Curl_uint_tbl_first(&multi->xfers, &mid, &entry)) { + multi_xfer_dump(multi, mid, entry); + while(Curl_uint_tbl_next(&multi->xfers, mid, &mid, &entry)) + multi_xfer_dump(multi, mid, entry); + } + fprintf(stderr, "===\n"); + fflush(stderr); } +#endif /* DEBUGBUILD */ diff --git a/lib/multi_ev.c b/lib/multi_ev.c index e62732a731..96595387c6 100644 --- a/lib/multi_ev.c +++ b/lib/multi_ev.c @@ -33,6 +33,9 @@ #include "timeval.h" #include "multi_ev.h" #include "select.h" +#include "uint-bset.h" +#include "uint-spbset.h" +#include "uint-table.h" #include "warnless.h" #include "multihandle.h" #include "socks.h" @@ -47,14 +50,13 @@ static void mev_in_callback(struct Curl_multi *multi, bool value) multi->in_callback = value; } -#define CURL_MEV_XFER_HASH_SIZE 13 #define CURL_MEV_CONN_HASH_SIZE 3 /* Information about a socket for which we inform the libcurl application * what to supervise (CURL_POLL_IN/CURL_POLL_OUT/CURL_POLL_REMOVE) */ struct mev_sh_entry { - struct Curl_hash_offt xfers; /* hash of transfers using this socket */ + struct uint_spbset xfers; /* bitset of transfers `mid`s on this socket */ struct Curl_hash_offt conns; /* hash of connections using this socket */ void *user_data; /* libcurl app data via curl_multi_assign() */ unsigned int action; /* CURL_POLL_IN/CURL_POLL_OUT we last told the @@ -81,7 +83,7 @@ static size_t mev_sh_entry_compare(void *k1, size_t k1_len, static void mev_sh_entry_dtor(void *freethis) { struct mev_sh_entry *entry = (struct mev_sh_entry *)freethis; - Curl_hash_offt_destroy(&entry->xfers); + Curl_uint_spbset_destroy(&entry->xfers); Curl_hash_offt_destroy(&entry->conns); free(entry); } @@ -114,7 +116,7 @@ mev_sh_entry_add(struct Curl_hash *sh, curl_socket_t s) if(!check) return NULL; /* major failure */ - Curl_hash_offt_init(&check->xfers, CURL_MEV_XFER_HASH_SIZE, NULL); + Curl_uint_spbset_init(&check->xfers); Curl_hash_offt_init(&check->conns, CURL_MEV_CONN_HASH_SIZE, NULL); /* make/add new hash entry */ @@ -134,13 +136,13 @@ static void mev_sh_entry_kill(struct Curl_multi *multi, curl_socket_t s) static size_t mev_sh_entry_user_count(struct mev_sh_entry *e) { - return Curl_hash_offt_count(&e->xfers) + Curl_hash_offt_count(&e->conns); + return Curl_uint_spbset_count(&e->xfers) + Curl_hash_offt_count(&e->conns); } static bool mev_sh_entry_xfer_known(struct mev_sh_entry *e, struct Curl_easy *data) { - return !!Curl_hash_offt_get(&e->xfers, data->mid); + return Curl_uint_spbset_contains(&e->xfers, data->mid); } static bool mev_sh_entry_conn_known(struct mev_sh_entry *e, @@ -154,7 +156,7 @@ static bool mev_sh_entry_xfer_add(struct mev_sh_entry *e, { /* detect weird values */ DEBUGASSERT(mev_sh_entry_user_count(e) < 100000); - return !!Curl_hash_offt_set(&e->xfers, data->mid, data); + return Curl_uint_spbset_add(&e->xfers, data->mid); } static bool mev_sh_entry_conn_add(struct mev_sh_entry *e, @@ -169,7 +171,10 @@ static bool mev_sh_entry_conn_add(struct mev_sh_entry *e, static bool mev_sh_entry_xfer_remove(struct mev_sh_entry *e, struct Curl_easy *data) { - return Curl_hash_offt_remove(&e->xfers, data->mid); + bool present = Curl_uint_spbset_contains(&e->xfers, data->mid); + if(present) + Curl_uint_spbset_remove(&e->xfers, data->mid); + return present; } static bool mev_sh_entry_conn_remove(struct mev_sh_entry *e, @@ -339,10 +344,10 @@ static CURLMcode mev_pollset_diff(struct Curl_multi *multi, return CURLM_OUT_OF_MEMORY; } CURL_TRC_M(data, "ev entry fd=%" FMT_SOCKET_T ", added %s #%" FMT_OFF_T - ", total=%zu/%zu (xfer/conn)", s, + ", total=%u/%zu (xfer/conn)", s, conn ? "connection" : "transfer", conn ? conn->connection_id : data->mid, - Curl_hash_offt_count(&entry->xfers), + Curl_uint_spbset_count(&entry->xfers), Curl_hash_offt_count(&entry->conns)); } else { @@ -409,8 +414,8 @@ static CURLMcode mev_pollset_diff(struct Curl_multi *multi, if(mresult) return mresult; CURL_TRC_M(data, "ev entry fd=%" FMT_SOCKET_T ", removed transfer, " - "total=%zu/%zu (xfer/conn)", s, - Curl_hash_offt_count(&entry->xfers), + "total=%u/%zu (xfer/conn)", s, + Curl_uint_spbset_count(&entry->xfers), Curl_hash_offt_count(&entry->conns)); } else { @@ -426,7 +431,7 @@ static CURLMcode mev_pollset_diff(struct Curl_multi *multi, } static struct easy_pollset* -mev_add_new_pollset(struct Curl_hash_offt *h, curl_off_t id) +mev_add_new_conn_pollset(struct Curl_hash_offt *h, curl_off_t id) { struct easy_pollset *ps; @@ -440,6 +445,21 @@ mev_add_new_pollset(struct Curl_hash_offt *h, curl_off_t id) return ps; } +static struct easy_pollset* +mev_add_new_xfer_pollset(struct uint_hash *h, unsigned int id) +{ + struct easy_pollset *ps; + + ps = calloc(1, sizeof(*ps)); + if(!ps) + return NULL; + if(!Curl_uint_hash_set(h, id, ps)) { + free(ps); + return NULL; + } + return ps; +} + static struct easy_pollset * mev_get_last_pollset(struct Curl_multi *multi, struct Curl_easy *data, @@ -449,7 +469,8 @@ mev_get_last_pollset(struct Curl_multi *multi, if(conn) return Curl_hash_offt_get(&multi->ev.conn_pollsets, conn->connection_id); - return Curl_hash_offt_get(&multi->ev.xfer_pollsets, data->mid); + else if(data) + return Curl_uint_hash_get(&multi->ev.xfer_pollsets, data->mid); } return NULL; } @@ -477,10 +498,11 @@ static CURLMcode mev_assess(struct Curl_multi *multi, if(!last_ps && ps.num) { if(conn) - last_ps = mev_add_new_pollset(&multi->ev.conn_pollsets, - conn->connection_id); + last_ps = mev_add_new_conn_pollset(&multi->ev.conn_pollsets, + conn->connection_id); else - last_ps = mev_add_new_pollset(&multi->ev.xfer_pollsets, data->mid); + last_ps = mev_add_new_xfer_pollset(&multi->ev.xfer_pollsets, + data->mid); if(!last_ps) return CURLM_OUT_OF_MEMORY; } @@ -506,16 +528,19 @@ CURLMcode Curl_multi_ev_assess_conn(struct Curl_multi *multi, return mev_assess(multi, data, conn); } -CURLMcode Curl_multi_ev_assess_xfer_list(struct Curl_multi *multi, - struct Curl_llist *list) +CURLMcode Curl_multi_ev_assess_xfer_bset(struct Curl_multi *multi, + struct uint_bset *set) { - struct Curl_llist_node *e; + unsigned int mid; CURLMcode result = CURLM_OK; - if(multi && multi->socket_cb) { - for(e = Curl_llist_head(list); e && !result; e = Curl_node_next(e)) { - result = Curl_multi_ev_assess_xfer(multi, Curl_node_elem(e)); + if(multi && multi->socket_cb && Curl_uint_bset_first(set, &mid)) { + do { + struct Curl_easy *data = Curl_multi_get_easy(multi, mid); + if(data) + result = Curl_multi_ev_assess_xfer(multi, data); } + while(!result && Curl_uint_bset_next(set, mid, &mid)); } return result; } @@ -532,21 +557,6 @@ CURLMcode Curl_multi_ev_assign(struct Curl_multi *multi, return CURLM_OK; } -static bool mev_xfer_expire_cb(curl_off_t id, void *value, void *user_data) -{ - const struct curltime *nowp = user_data; - struct Curl_easy *data = value; - - DEBUGASSERT(data); - DEBUGASSERT(data->magic == CURLEASY_MAGIC_NUMBER); - if(data && id >= 0) { - /* Expire with out current now, so we will get it below when - * asking the splaytree for expired transfers. */ - Curl_expire_ex(data, nowp, 0, EXPIRE_RUN_NOW); - } - return TRUE; -} - void Curl_multi_ev_expire_xfers(struct Curl_multi *multi, curl_socket_t s, const struct curltime *nowp, @@ -563,8 +573,20 @@ void Curl_multi_ev_expire_xfers(struct Curl_multi *multi, asked to get removed, so thus we better survive stray socket actions and just move on. */ if(entry) { - Curl_hash_offt_visit(&entry->xfers, mev_xfer_expire_cb, - CURL_UNCONST(nowp)); + struct Curl_easy *data; + unsigned int mid; + + if(Curl_uint_spbset_first(&entry->xfers, &mid)) { + do { + data = Curl_multi_get_easy(multi, mid); + if(data) { + /* Expire with out current now, so we will get it below when + * asking the splaytree for expired transfers. */ + Curl_expire_ex(data, nowp, 0, EXPIRE_RUN_NOW); + } + } + while(Curl_uint_spbset_next(&entry->xfers, mid, &mid)); + } if(Curl_hash_offt_count(&entry->conns)) *run_cpool = TRUE; @@ -581,9 +603,9 @@ void Curl_multi_ev_xfer_done(struct Curl_multi *multi, struct Curl_easy *data) { DEBUGASSERT(!data->conn); /* transfer should have been detached */ - if(data->mid >= 0) { + if(data != multi->admin) { (void)mev_assess(multi, data, NULL); - Curl_hash_offt_remove(&multi->ev.xfer_pollsets, data->mid); + Curl_uint_hash_remove(&multi->ev.xfer_pollsets, data->mid); } } @@ -597,7 +619,13 @@ void Curl_multi_ev_conn_done(struct Curl_multi *multi, #define CURL_MEV_PS_HASH_SLOTS (991) /* nice prime */ -static void mev_hash_pollset_free(curl_off_t id, void *entry) +static void mev_hash_conn_pollset_free(curl_off_t id, void *entry) +{ + (void)id; + free(entry); +} + +static void mev_hash_xfer_pollset_free(unsigned int id, void *entry) { (void)id; free(entry); @@ -607,15 +635,15 @@ void Curl_multi_ev_init(struct Curl_multi *multi, size_t hashsize) { Curl_hash_init(&multi->ev.sh_entries, hashsize, mev_sh_entry_hash, mev_sh_entry_compare, mev_sh_entry_dtor); - Curl_hash_offt_init(&multi->ev.xfer_pollsets, - CURL_MEV_PS_HASH_SLOTS, mev_hash_pollset_free); + Curl_uint_hash_init(&multi->ev.xfer_pollsets, + CURL_MEV_PS_HASH_SLOTS, mev_hash_xfer_pollset_free); Curl_hash_offt_init(&multi->ev.conn_pollsets, - CURL_MEV_PS_HASH_SLOTS, mev_hash_pollset_free); + CURL_MEV_PS_HASH_SLOTS, mev_hash_conn_pollset_free); } void Curl_multi_ev_cleanup(struct Curl_multi *multi) { Curl_hash_destroy(&multi->ev.sh_entries); - Curl_hash_offt_destroy(&multi->ev.xfer_pollsets); + Curl_uint_hash_destroy(&multi->ev.xfer_pollsets); Curl_hash_offt_destroy(&multi->ev.conn_pollsets); } diff --git a/lib/multi_ev.h b/lib/multi_ev.h index 20e052e003..3aa6cca24c 100644 --- a/lib/multi_ev.h +++ b/lib/multi_ev.h @@ -30,10 +30,11 @@ struct Curl_easy; struct Curl_multi; struct easy_pollset; +struct uint_bset; struct curl_multi_ev { struct Curl_hash sh_entries; - struct Curl_hash_offt xfer_pollsets; + struct uint_hash xfer_pollsets; struct Curl_hash_offt conn_pollsets; }; @@ -53,8 +54,8 @@ CURLMcode Curl_multi_ev_assign(struct Curl_multi *multi, curl_socket_t s, CURLMcode Curl_multi_ev_assess_xfer(struct Curl_multi *multi, struct Curl_easy *data); /* Assess all easy handles on the list */ -CURLMcode Curl_multi_ev_assess_xfer_list(struct Curl_multi *multi, - struct Curl_llist *list); +CURLMcode Curl_multi_ev_assess_xfer_bset(struct Curl_multi *multi, + struct uint_bset *set); /* Assess the connection by getting its current pollset */ CURLMcode Curl_multi_ev_assess_conn(struct Curl_multi *multi, struct Curl_easy *data, diff --git a/lib/multihandle.h b/lib/multihandle.h index d3d66074e9..04db02f0b1 100644 --- a/lib/multihandle.h +++ b/lib/multihandle.h @@ -32,6 +32,9 @@ #include "multi_ev.h" #include "psl.h" #include "socketpair.h" +#include "uint-bset.h" +#include "uint-spbset.h" +#include "uint-table.h" struct connectdata; struct Curl_easy; @@ -90,19 +93,18 @@ struct Curl_multi { this multi handle with an easy handle. Set this to CURL_MULTI_HANDLE. */ unsigned int magic; - unsigned int num_easy; /* amount of entries in the linked list above. */ - unsigned int num_alive; /* amount of easy handles that are added but have - not yet reached COMPLETE state */ + unsigned int xfers_alive; /* amount of added transfers that have + not yet reached COMPLETE state */ + struct uint_tbl xfers; /* transfers added to this multi */ + /* Each transfer's mid may be present in at most one of these */ + struct uint_bset process; /* transfer being processed */ + struct uint_bset pending; /* transfers in waiting (conn limit etc.) */ + struct uint_bset msgsent; /* transfers done with message for application */ struct Curl_llist msglist; /* a list of messages from completed transfers */ - /* Each added easy handle is added to ONE of these three lists */ - struct Curl_llist process; /* not in PENDING or MSGSENT */ - struct Curl_llist pending; /* in PENDING */ - struct Curl_llist msgsent; /* in MSGSENT */ - curl_off_t next_easy_mid; /* next multi-id for easy handle added */ - - struct Curl_easy *admin; /* internal easy handle for admin operations */ + struct Curl_easy *admin; /* internal easy handle for admin operations. + gets assigned `mid` 0 on multi init */ /* callback function and user data pointer for the *socket() API */ curl_socket_callback socket_cb; diff --git a/lib/multiif.h b/lib/multiif.h index 940d962c6c..eae634ab40 100644 --- a/lib/multiif.h +++ b/lib/multiif.h @@ -47,7 +47,8 @@ void Curl_multi_connchanged(struct Curl_multi *multi); /* Internal version of curl_multi_init() accepts size parameters for the socket, connection and dns hashes */ -struct Curl_multi *Curl_multi_handle(size_t hashsize, +struct Curl_multi *Curl_multi_handle(unsigned int xfer_table_size, + size_t hashsize, size_t chashsize, size_t dnssize, size_t sesssize); @@ -163,9 +164,13 @@ CURLcode Curl_multi_xfer_sockbuf_borrow(struct Curl_easy *data, void Curl_multi_xfer_sockbuf_release(struct Curl_easy *data, char *buf); /** - * Get the transfer handle for the given id. Returns NULL if not found. + * Get the easy handle for the given mid. + * Returns NULL if not found. */ -struct Curl_easy *Curl_multi_get_handle(struct Curl_multi *multi, - curl_off_t id); +struct Curl_easy *Curl_multi_get_easy(struct Curl_multi *multi, + unsigned int mid); + +/* Get the # of transfers current in process/pending. */ +unsigned int Curl_multi_xfers_running(struct Curl_multi *multi); #endif /* HEADER_CURL_MULTIIF_H */ diff --git a/lib/share.c b/lib/share.c index 721030f260..d1ab55eb27 100644 --- a/lib/share.c +++ b/lib/share.c @@ -52,6 +52,8 @@ curl_share_init(void) free(share); return NULL; } + /* admin handles have mid 0 */ + share->admin->mid = 0; share->admin->state.internal = TRUE; #ifdef DEBUGBUILD if(getenv("CURL_DEBUG")) diff --git a/lib/uint-bset.c b/lib/uint-bset.c new file mode 100644 index 0000000000..2560b37363 --- /dev/null +++ b/lib/uint-bset.c @@ -0,0 +1,238 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ + +#include "curl_setup.h" +#include "uint-bset.h" + +/* The last 3 #include files should be in this order */ +#include "curl_printf.h" +#include "curl_memory.h" +#include "memdebug.h" + +#ifdef DEBUGBUILD +#define CURL_UINT_BSET_MAGIC 0x62757473 +#endif + +void Curl_uint_bset_init(struct uint_bset *bset) +{ + memset(bset, 0, sizeof(*bset)); +#ifdef DEBUGBUILD + bset->init = CURL_UINT_BSET_MAGIC; +#endif +} + + +CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax) +{ + unsigned int nslots = (nmax + 63) / 64; + + DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC); + if(nslots != bset->nslots) { + curl_uint64_t *slots = calloc(nslots, sizeof(curl_uint64_t)); + if(!slots) + return CURLE_OUT_OF_MEMORY; + + if(bset->slots) { + memcpy(slots, bset->slots, + (CURLMIN(nslots, bset->nslots) * sizeof(curl_uint64_t))); + free(bset->slots); + } + bset->slots = slots; + bset->nslots = nslots; + } + return CURLE_OK; +} + + +void Curl_uint_bset_destroy(struct uint_bset *bset) +{ + DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC); + free(bset->slots); + memset(bset, 0, sizeof(*bset)); +} + + +unsigned int Curl_uint_bset_capacity(struct uint_bset *bset) +{ + return bset->nslots * 64; +} + + +unsigned int Curl_uint_bset_count(struct uint_bset *bset) +{ + unsigned int i; + unsigned int n = 0; + for(i = 0; i < bset->nslots; ++i) { + if(bset->slots[i]) + n += CURL_POPCOUNT64(bset->slots[i]); + } + return n; +} + + +bool Curl_uint_bset_empty(struct uint_bset *bset) +{ + unsigned int i; + for(i = 0; i < bset->nslots; ++i) { + if(bset->slots[i]) + return FALSE; + } + return TRUE; +} + + +void Curl_uint_bset_clear(struct uint_bset *bset) +{ + if(bset->nslots) + memset(bset->slots, 0, bset->nslots * sizeof(curl_uint64_t)); +} + + +bool Curl_uint_bset_add(struct uint_bset *bset, unsigned int i) +{ + unsigned int islot = i / 64; + if(islot >= bset->nslots) + return FALSE; + bset->slots[islot] |= ((curl_uint64_t)1 << (i % 64)); + return TRUE; +} + + +void Curl_uint_bset_remove(struct uint_bset *bset, unsigned int i) +{ + size_t islot = i / 64; + if(islot < bset->nslots) + bset->slots[islot] &= ~((curl_uint64_t)1 << (i % 64)); +} + + +bool Curl_uint_bset_contains(struct uint_bset *bset, unsigned int i) +{ + unsigned int islot = i / 64; + if(islot >= bset->nslots) + return FALSE; + return (bset->slots[islot] & ((curl_uint64_t)1 << (i % 64))) != 0; +} + + +bool Curl_uint_bset_first(struct uint_bset *bset, unsigned int *pfirst) +{ + unsigned int i; + for(i = 0; i < bset->nslots; ++i) { + if(bset->slots[i]) { + *pfirst = (i * 64) + CURL_CTZ64(bset->slots[i]); + return TRUE; + } + } + *pfirst = UINT_MAX; /* a value we cannot store */ + return FALSE; +} + +bool Curl_uint_bset_next(struct uint_bset *bset, unsigned int last, + unsigned int *pnext) +{ + unsigned int islot; + curl_uint64_t x; + + ++last; /* look for number one higher than last */ + islot = last / 64; /* the slot this would be in */ + if(islot < bset->nslots) { + /* shift away the bits we already iterated in this slot */ + x = (bset->slots[islot] >> (last % 64)); + if(x) { + /* more bits set, next is `last` + trailing0s of the shifted slot */ + *pnext = last + CURL_CTZ64(x); + return TRUE; + } + /* no more bits set in the last slot, scan forward */ + for(islot = islot + 1; islot < bset->nslots; ++islot) { + if(bset->slots[islot]) { + *pnext = (islot * 64) + CURL_CTZ64(bset->slots[islot]); + return TRUE; + } + } + } + *pnext = UINT_MAX; /* a value we cannot store */ + return FALSE; +} + +#ifdef CURL_POPCOUNT64_IMPLEMENT +unsigned int Curl_popcount64(curl_uint64_t x) +{ + /* Compute the "Hamming Distance" between 'x' and 0, + * which is the number of set bits in 'x'. + * See: https://en.wikipedia.org/wiki/Hamming_weight */ + const curl_uint64_t m1 = CURL_OFF_TU_C(0x5555555555555555); /* 0101+ */ + const curl_uint64_t m2 = CURL_OFF_TU_C(0x3333333333333333); /* 00110011+ */ + const curl_uint64_t m4 = CURL_OFF_TU_C(0x0f0f0f0f0f0f0f0f); /* 00001111+ */ + /* 1 + 256^1 + 256^2 + 256^3 + ... + 256^7 */ + const curl_uint64_t h01 = CURL_OFF_TU_C(0x0101010101010101); + x -= (x >> 1) & m1; /* replace every 2 bits with bits present */ + x = (x & m2) + ((x >> 2) & m2); /* replace every nibble with bits present */ + x = (x + (x >> 4)) & m4; /* replace every byte with bits present */ + /* top 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... which makes the + * top byte the sum of all individual 8 bytes, throw away the rest */ + return (unsigned int)((x * h01) >> 56); +} +#endif /* CURL_POPCOUNT64_IMPLEMENT */ + + +#ifdef CURL_CTZ64_IMPLEMENT +unsigned int Curl_ctz64(curl_uint64_t x) +{ + /* count trailing zeros in a curl_uint64_t. + * divide and conquer to find the number of lower 0 bits */ + const curl_uint64_t ml32 = CURL_OFF_TU_C(0xFFFFFFFF); /* lower 32 bits */ + const curl_uint64_t ml16 = CURL_OFF_TU_C(0x0000FFFF); /* lower 16 bits */ + const curl_uint64_t ml8 = CURL_OFF_TU_C(0x000000FF); /* lower 8 bits */ + const curl_uint64_t ml4 = CURL_OFF_TU_C(0x0000000F); /* lower 4 bits */ + const curl_uint64_t ml2 = CURL_OFF_TU_C(0x00000003); /* lower 2 bits */ + unsigned int n; + + if(!x) + return 64; + n = 1; + if(!(x & ml32)) { + n = n + 32; + x = x >> 32; + } + if(!(x & ml16)) { + n = n + 16; + x = x >> 16; + } + if(!(x & ml8)) { + n = n + 8; + x = x >> 8; + } + if(!(x & ml4)) { + n = n + 4; + x = x >> 4; + } + if(!(x & ml2)) { + n = n + 2; + x = x >> 2; + } + return n - (unsigned int)(x & 1); +} +#endif /* CURL_CTZ64_IMPLEMENT */ diff --git a/lib/uint-bset.h b/lib/uint-bset.h new file mode 100644 index 0000000000..d998dccdfe --- /dev/null +++ b/lib/uint-bset.h @@ -0,0 +1,114 @@ +#ifndef HEADER_CURL_UINT_BSET_H +#define HEADER_CURL_UINT_BSET_H +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curl_setup.h" + +#include + +/* A bitset for unsigned int values. + * It can hold the numbers from 0 - (nmax - 1), + * rounded to the next 64 multiple. + * + * Optimized for high efficiency in adding/removing numbers. + * Efficient storage when the set is (often) relatively full. + * + * If the set's cardinality is only expected to be a fraction of nmax, + * uint_spbset offers a "sparse" variant with more memory efficiency at + * the price of slightly slower operations. + */ + +struct uint_bset { + curl_uint64_t *slots; + unsigned int nslots; +#ifdef DEBUGBUILD + int init; +#endif +}; + +/* Initialize the bitset with capacity 0. */ +void Curl_uint_bset_init(struct uint_bset *bset); + +/* Resize the bitset capacity to hold numbers from 0 to `nmax`, + * which rounds up `nmax` to the next multiple of 64. */ +CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax); + +/* Destroy the bitset, freeing all resources. */ +void Curl_uint_bset_destroy(struct uint_bset *bset); + +/* Get the bitset capacity, e.g. can hold numbers from 0 to capacity - 1. */ +unsigned int Curl_uint_bset_capacity(struct uint_bset *bset); + +/* Get the cardinality of the bitset, e.g. numbers present in the set. */ +unsigned int Curl_uint_bset_count(struct uint_bset *bset); + +/* TRUE of bitset is empty */ +bool Curl_uint_bset_empty(struct uint_bset *bset); + +/* Clear the bitset, making it empty. */ +void Curl_uint_bset_clear(struct uint_bset *bset); + +/* Add the number `i` to the bitset. Return FALSE if the number is + * outside the set's capacity. + * Numbers can be added more than once, without making a difference. */ +bool Curl_uint_bset_add(struct uint_bset *bset, unsigned int i); + +/* Remove the number `i` from the bitset. */ +void Curl_uint_bset_remove(struct uint_bset *bset, unsigned int i); + +/* Return TRUE if the bitset contains number `i`. */ +bool Curl_uint_bset_contains(struct uint_bset *bset, unsigned int i); + +/* Get the first number in the bitset, e.g. the smallest. + * Returns FALSE when the bitset is empty. */ +bool Curl_uint_bset_first(struct uint_bset *bset, unsigned int *pfirst); + +/* Get the next number in the bitset, following `last` in natural order. + * Put another way, this is the smallest number greater than `last` in + * the bitset. `last` does not have to be present in the set. + * + * Returns FALSE when no such number is in the set. + * + * This allows to iterate the set while being modified: + * - added numbers higher than 'last' will be picked up by the iteration. + * - added numbers lower than 'last' will not show up. + * - removed numbers lower or equal to 'last' will not show up. + * - removed numbers higher than 'last' will not be visited. */ +bool Curl_uint_bset_next(struct uint_bset *bset, unsigned int last, + unsigned int *pnext); + + +#ifndef CURL_POPCOUNT64 +#define CURL_POPCOUNT64(x) Curl_popcount64(x) +#define CURL_POPCOUNT64_IMPLEMENT +unsigned int Curl_popcount64(curl_uint64_t x); +#endif /* !CURL_POPCOUNT64 */ + +#ifndef CURL_CTZ64 +#define CURL_CTZ64(x) Curl_ctz64(x) +#define CURL_CTZ64_IMPLEMENT +unsigned int Curl_ctz64(curl_uint64_t x); +#endif /* !CURL_CTZ64 */ + +#endif /* HEADER_CURL_UINT_BSET_H */ diff --git a/lib/uint-spbset.c b/lib/uint-spbset.c new file mode 100644 index 0000000000..578b9bd07c --- /dev/null +++ b/lib/uint-spbset.c @@ -0,0 +1,273 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ + +#include "curl_setup.h" +#include "uint-bset.h" +#include "uint-spbset.h" + +/* The last 3 #include files should be in this order */ +#include "curl_printf.h" +#include "curl_memory.h" +#include "memdebug.h" + +#ifdef DEBUGBUILD +#define CURL_UINT_SPBSET_MAGIC 0x70737362 +#endif + +void Curl_uint_spbset_init(struct uint_spbset *bset) +{ + memset(bset, 0, sizeof(*bset)); +#ifdef DEBUGBUILD + bset->init = CURL_UINT_SPBSET_MAGIC; +#endif +} + +void Curl_uint_spbset_destroy(struct uint_spbset *bset) +{ + DEBUGASSERT(bset->init == CURL_UINT_SPBSET_MAGIC); + Curl_uint_spbset_clear(bset); +} + +unsigned int Curl_uint_spbset_count(struct uint_spbset *bset) +{ + struct uint_spbset_chunk *chunk; + unsigned int i, n = 0; + + for(chunk = &bset->head; chunk; chunk = chunk->next) { + for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { + if(chunk->slots[i]) + n += CURL_POPCOUNT64(chunk->slots[i]); + } + } + return n; +} + +bool Curl_uint_spbset_empty(struct uint_spbset *bset) +{ + struct uint_spbset_chunk *chunk; + unsigned int i; + + for(chunk = &bset->head; chunk; chunk = chunk->next) { + for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { + if(chunk->slots[i]) + return FALSE; + } + } + return TRUE; +} + +void Curl_uint_spbset_clear(struct uint_spbset *bset) +{ + struct uint_spbset_chunk *next, *chunk; + + for(chunk = bset->head.next; chunk; chunk = next) { + next = chunk->next; + free(chunk); + } + memset(&bset->head, 0, sizeof(bset->head)); +} + + +static struct uint_spbset_chunk * +uint_spbset_get_chunk(struct uint_spbset *bset, unsigned int i, bool grow) +{ + struct uint_spbset_chunk *chunk, **panchor = NULL; + unsigned int i_offset = (i & ~CURL_UINT_SPBSET_CH_MASK); + + if(!bset) + return NULL; + + for(chunk = &bset->head; chunk; + panchor = &chunk->next, chunk = chunk->next) { + if(chunk->offset == i_offset) { + return chunk; + } + else if(chunk->offset > i_offset) { + /* need new chunk here */ + chunk = NULL; + break; + } + } + + if(!grow) + return NULL; + + /* need a new one */ + chunk = calloc(1, sizeof(*chunk)); + if(!chunk) + return NULL; + + if(panchor) { /* insert between panchor and *panchor */ + chunk->next = *panchor; + *panchor = chunk; + } + else { /* prepend to head, switching places */ + memcpy(chunk, &bset->head, sizeof(*chunk)); + memset(&bset->head, 0, sizeof(bset->head)); + bset->head.next = chunk; + } + chunk->offset = i_offset; + return chunk; +} + + +bool Curl_uint_spbset_add(struct uint_spbset *bset, unsigned int i) +{ + struct uint_spbset_chunk *chunk; + unsigned int i_chunk; + + chunk = uint_spbset_get_chunk(bset, i, TRUE); + if(!chunk) + return FALSE; + + DEBUGASSERT(i >= chunk->offset); + i_chunk = (i - chunk->offset); + DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); + chunk->slots[(i_chunk / 64)] |= ((curl_uint64_t)1 << (i_chunk % 64)); + return TRUE; +} + + +void Curl_uint_spbset_remove(struct uint_spbset *bset, unsigned int i) +{ + struct uint_spbset_chunk *chunk; + unsigned int i_chunk; + + chunk = uint_spbset_get_chunk(bset, i, FALSE); + if(chunk) { + DEBUGASSERT(i >= chunk->offset); + i_chunk = (i - chunk->offset); + DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); + chunk->slots[(i_chunk / 64)] &= ~((curl_uint64_t)1 << (i_chunk % 64)); + } +} + + +bool Curl_uint_spbset_contains(struct uint_spbset *bset, unsigned int i) +{ + struct uint_spbset_chunk *chunk; + unsigned int i_chunk; + + chunk = uint_spbset_get_chunk(bset, i, FALSE); + if(chunk) { + DEBUGASSERT(i >= chunk->offset); + i_chunk = (i - chunk->offset); + DEBUGASSERT((i_chunk / 64) < CURL_UINT_SPBSET_CH_SLOTS); + return (chunk->slots[i_chunk / 64] & + ((curl_uint64_t)1 << (i_chunk % 64))) != 0; + } + return FALSE; +} + +bool Curl_uint_spbset_first(struct uint_spbset *bset, unsigned int *pfirst) +{ + struct uint_spbset_chunk *chunk; + unsigned int i; + + for(chunk = &bset->head; chunk; chunk = chunk->next) { + for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { + if(chunk->slots[i]) { + *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); + return TRUE; + } + } + } + *pfirst = 0; /* give it a defined value even if it should not be used */ + return FALSE; +} + + +static bool uint_spbset_chunk_first(struct uint_spbset_chunk *chunk, + unsigned int *pfirst) +{ + unsigned int i; + for(i = 0; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { + if(chunk->slots[i]) { + *pfirst = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); + return TRUE; + } + } + *pfirst = UINT_MAX; /* a value we cannot store */ + return FALSE; +} + + +static bool uint_spbset_chunk_next(struct uint_spbset_chunk *chunk, + unsigned int last, + unsigned int *pnext) +{ + if(chunk->offset <= last) { + curl_uint64_t x; + unsigned int i = ((last - chunk->offset) / 64); + if(i < CURL_UINT_SPBSET_CH_SLOTS) { + x = (chunk->slots[i] >> (last % 64)); + if(x) { + /* more bits set, next is `last` + trailing0s of the shifted slot */ + *pnext = last + CURL_CTZ64(x); + return TRUE; + } + /* no more bits set in the last slot, scan forward */ + for(i = i + 1; i < CURL_UINT_SPBSET_CH_SLOTS; ++i) { + if(chunk->slots[i]) { + *pnext = chunk->offset + ((i * 64) + CURL_CTZ64(chunk->slots[i])); + return TRUE; + } + } + } + } + *pnext = UINT_MAX; + return FALSE; +} + +bool Curl_uint_spbset_next(struct uint_spbset *bset, unsigned int last, + unsigned int *pnext) +{ + struct uint_spbset_chunk *chunk; + unsigned int last_offset; + + ++last; /* look for the next higher number */ + last_offset = (last & ~CURL_UINT_SPBSET_CH_MASK); + + for(chunk = &bset->head; chunk; chunk = chunk->next) { + if(chunk->offset >= last_offset) { + break; + } + } + + if(chunk && (chunk->offset == last_offset)) { + /* is there a number higher than last in this chunk? */ + if(uint_spbset_chunk_next(chunk, last, pnext)) + return TRUE; + /* not in this chunk */ + chunk = chunk->next; + } + /* look for the first in the "higher" chunks, if there are any. */ + while(chunk) { + if(uint_spbset_chunk_first(chunk, pnext)) + return TRUE; + chunk = chunk->next; + } + *pnext = UINT_MAX; + return FALSE; +} diff --git a/lib/uint-spbset.h b/lib/uint-spbset.h new file mode 100644 index 0000000000..571d56753c --- /dev/null +++ b/lib/uint-spbset.h @@ -0,0 +1,99 @@ +#ifndef HEADER_CURL_UINT_SPBSET_H +#define HEADER_CURL_UINT_SPBSET_H +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curl_setup.h" + +#include + +/* A "sparse" bitset for unsigned int values. + * It can hold any unsigned int value. + * + * Optimized for the case where only a small set of numbers need + * to be kept, especially when "close" together. Then storage space + * is most efficient, deteriorating when many number are far apart. + */ + +/* 4 slots = 256 bits, keep this a 2^n value. */ +#define CURL_UINT_SPBSET_CH_SLOTS 4 +#define CURL_UINT_SPBSET_CH_MASK ((CURL_UINT_SPBSET_CH_SLOTS * 64) - 1) + +/* store the uint value from offset to + * (offset + (CURL_UINT_SPBSET_CHUNK_SLOTS * 64) - 1 */ +struct uint_spbset_chunk { + struct uint_spbset_chunk *next; + curl_uint64_t slots[CURL_UINT_SPBSET_CH_SLOTS]; + unsigned int offset; +}; + +struct uint_spbset { + struct uint_spbset_chunk head; +#ifdef DEBUGBUILD + int init; +#endif +}; + +void Curl_uint_spbset_init(struct uint_spbset *bset); + +void Curl_uint_spbset_destroy(struct uint_spbset *bset); + +/* Get the cardinality of the bitset, e.g. numbers present in the set. */ +unsigned int Curl_uint_spbset_count(struct uint_spbset *bset); + +/* TRUE of bitset is empty */ +bool Curl_uint_spbset_empty(struct uint_spbset *bset); + +/* Clear the bitset, making it empty. */ +void Curl_uint_spbset_clear(struct uint_spbset *bset); + +/* Add the number `i` to the bitset. + * Numbers can be added more than once, without making a difference. + * Returns FALSE if allocations failed. */ +bool Curl_uint_spbset_add(struct uint_spbset *bset, unsigned int i); + +/* Remove the number `i` from the bitset. */ +void Curl_uint_spbset_remove(struct uint_spbset *bset, unsigned int i); + +/* Return TRUE if the bitset contains number `i`. */ +bool Curl_uint_spbset_contains(struct uint_spbset *bset, unsigned int i); + +/* Get the first number in the bitset, e.g. the smallest. + * Returns FALSE when the bitset is empty. */ +bool Curl_uint_spbset_first(struct uint_spbset *bset, unsigned int *pfirst); + +/* Get the next number in the bitset, following `last` in natural order. + * Put another way, this is the smallest number greater than `last` in + * the bitset. `last` does not have to be present in the set. + * + * Returns FALSE when no such number is in the set. + * + * This allows to iterate the set while being modified: + * - added numbers higher than 'last' will be picked up by the iteration. + * - added numbers lower than 'last' will not show up. + * - removed numbers lower or equal to 'last' will not show up. + * - removed numbers higher than 'last' will not be visited. */ +bool Curl_uint_spbset_next(struct uint_spbset *bset, unsigned int last, + unsigned int *pnext); + +#endif /* HEADER_CURL_UINT_SPBSET_H */ diff --git a/lib/uint-table.c b/lib/uint-table.c new file mode 100644 index 0000000000..d8de1b128a --- /dev/null +++ b/lib/uint-table.c @@ -0,0 +1,214 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ + +#include "curl_setup.h" +#include "uint-table.h" + +/* The last 3 #include files should be in this order */ +#include "curl_printf.h" +#include "curl_memory.h" +#include "memdebug.h" + +#ifdef DEBUGBUILD +#define CURL_UINT_TBL_MAGIC 0x62757473 +#endif + +void Curl_uint_tbl_init(struct uint_tbl *tbl, + Curl_uint_tbl_entry_dtor *entry_dtor) +{ + memset(tbl, 0, sizeof(*tbl)); + tbl->entry_dtor = entry_dtor; + tbl->last_key_added = UINT_MAX; +#ifdef DEBUGBUILD + tbl->init = CURL_UINT_TBL_MAGIC; +#endif +} + + +static void uint_tbl_clear_rows(struct uint_tbl *tbl, + unsigned int from, + unsigned int upto_excluding) +{ + unsigned int i, end; + + end = CURLMIN(upto_excluding, tbl->nrows); + for(i = from; i < end; ++i) { + if(tbl->rows[i]) { + if(tbl->entry_dtor) + tbl->entry_dtor(i, tbl->rows[i]); + tbl->rows[i] = NULL; + tbl->nentries--; + } + } +} + + +CURLcode Curl_uint_tbl_resize(struct uint_tbl *tbl, unsigned int nrows) +{ + /* we use `tbl->nrows + 1` during iteration, want that to work */ + DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); + if(!nrows || (nrows == UINT_MAX)) + return CURLE_BAD_FUNCTION_ARGUMENT; + if(nrows != tbl->nrows) { + void **rows = calloc(nrows, sizeof(void *)); + if(!rows) + return CURLE_OUT_OF_MEMORY; + if(tbl->rows) { + memcpy(rows, tbl->rows, (CURLMIN(nrows, tbl->nrows) * sizeof(void *))); + if(nrows < tbl->nrows) + uint_tbl_clear_rows(tbl, nrows, tbl->nrows); + free(tbl->rows); + } + tbl->rows = rows; + tbl->nrows = nrows; + } + return CURLE_OK; +} + + +void Curl_uint_tbl_destroy(struct uint_tbl *tbl) +{ + DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); + Curl_uint_tbl_clear(tbl); + free(tbl->rows); + memset(tbl, 0, sizeof(*tbl)); +} + + +void Curl_uint_tbl_clear(struct uint_tbl *tbl) +{ + DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); + uint_tbl_clear_rows(tbl, 0, tbl->nrows); + DEBUGASSERT(!tbl->nentries); + tbl->last_key_added = UINT_MAX; +} + + +unsigned int Curl_uint_tbl_capacity(struct uint_tbl *tbl) +{ + return tbl->nrows; +} + + +unsigned int Curl_uint_tbl_count(struct uint_tbl *tbl) +{ + return tbl->nentries; +} + + +void *Curl_uint_tbl_get(struct uint_tbl *tbl, unsigned int key) +{ + return (key < tbl->nrows) ? tbl->rows[key] : NULL; +} + + +bool Curl_uint_tbl_add(struct uint_tbl *tbl, void *entry, unsigned int *pkey) +{ + unsigned int key, start_pos; + + DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); + if(!entry || !pkey) + return FALSE; + *pkey = UINT_MAX; /* always invalid */ + if(tbl->nentries == tbl->nrows) /* full */ + return FALSE; + + start_pos = CURLMIN(tbl->last_key_added, tbl->nrows) + 1; + for(key = start_pos; key < tbl->nrows; ++key) { + if(!tbl->rows[key]) { + tbl->rows[key] = entry; + tbl->nentries++; + tbl->last_key_added = key; + *pkey = key; + return TRUE; + } + } + /* no free entry at or above tbl->maybe_next_key, wrap around */ + for(key = 0; key < start_pos; ++key) { + if(!tbl->rows[key]) { + tbl->rows[key] = entry; + tbl->nentries++; + tbl->last_key_added = key; + *pkey = key; + return TRUE; + } + } + /* Did not find any free row? Should not happen */ + DEBUGASSERT(0); + return FALSE; +} + + +void Curl_uint_tbl_remove(struct uint_tbl *tbl, unsigned int key) +{ + uint_tbl_clear_rows(tbl, key, key + 1); +} + + +bool Curl_uint_tbl_contains(struct uint_tbl *tbl, unsigned int key) +{ + return (key < tbl->nrows) ? !!tbl->rows[key] : FALSE; +} + + +static bool uint_tbl_next_at(struct uint_tbl *tbl, unsigned int key, + unsigned int *pkey, void **pentry) +{ + for(; key < tbl->nrows; ++key) { + if(tbl->rows[key]) { + *pkey = key; + *pentry = tbl->rows[key]; + return TRUE; + } + } + *pkey = UINT_MAX; /* always invalid */ + *pentry = NULL; + return FALSE; +} + +bool Curl_uint_tbl_first(struct uint_tbl *tbl, + unsigned int *pkey, void **pentry) +{ + if(!pkey || !pentry) + return FALSE; + if(tbl->nentries && uint_tbl_next_at(tbl, 0, pkey, pentry)) + return TRUE; + DEBUGASSERT(!tbl->nentries); + *pkey = UINT_MAX; /* always invalid */ + *pentry = NULL; + return FALSE; +} + + +bool Curl_uint_tbl_next(struct uint_tbl *tbl, unsigned int last_key, + unsigned int *pkey, void **pentry) +{ + if(!pkey || !pentry) + return FALSE; + if(uint_tbl_next_at(tbl, last_key + 1, pkey, pentry)) + return TRUE; + *pkey = UINT_MAX; /* always invalid */ + *pentry = NULL; + return FALSE; +} diff --git a/lib/uint-table.h b/lib/uint-table.h new file mode 100644 index 0000000000..2d8e86498a --- /dev/null +++ b/lib/uint-table.h @@ -0,0 +1,101 @@ +#ifndef HEADER_CURL_UINT_TABLE_H +#define HEADER_CURL_UINT_TABLE_H +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curl_setup.h" + +#include + +/* Destructor for a single table entry */ +typedef void Curl_uint_tbl_entry_dtor(unsigned int key, void *entry); + +struct uint_tbl { + void **rows; /* array of void* holding entries */ + Curl_uint_tbl_entry_dtor *entry_dtor; + unsigned int nrows; /* length of `rows` array */ + unsigned int nentries; /* entris in table */ + unsigned int last_key_added; /* UINT_MAX or last key added */ +#ifdef DEBUGBUILD + int init; +#endif +}; + +/* Initialize the table with 0 capacity. + * The optional `entry_dtor` is called when a table entry is removed, + * Passing NULL means no action is taken on removal. */ +void Curl_uint_tbl_init(struct uint_tbl *tbl, + Curl_uint_tbl_entry_dtor *entry_dtor); + +/* Resize the table to change capacity `nmax`. When `nmax` is reduced, + * all present entries with key equal or larger to `nmax` are removed. */ +CURLcode Curl_uint_tbl_resize(struct uint_tbl *tbl, unsigned int nmax); + +/* Destroy the table, freeing all entries. */ +void Curl_uint_tbl_destroy(struct uint_tbl *tbl); + +/* Get the table capacity. */ +unsigned int Curl_uint_tbl_capacity(struct uint_tbl *tbl); + +/* Get the number of entries in the table. */ +unsigned int Curl_uint_tbl_count(struct uint_tbl *tbl); + +/* Clear the table, making it empty. */ +void Curl_uint_tbl_clear(struct uint_tbl *tbl); + +/* Get the entry for key or NULL if not present */ +void *Curl_uint_tbl_get(struct uint_tbl *tbl, unsigned int key); + +/* Add a new entry to the table and assign it a free key. + * Returns FALSE if the table is full. + * + * Keys are assigned in a round-robin manner. + * No matter the capacity, UINT_MAX is never assigned. */ +bool Curl_uint_tbl_add(struct uint_tbl *tbl, void *entry, unsigned int *pkey); + +/* Remove the entry with `key`. */ +void Curl_uint_tbl_remove(struct uint_tbl *tbl, unsigned int key); + +/* Return TRUE if the table contains an tryn with that keys. */ +bool Curl_uint_tbl_contains(struct uint_tbl *tbl, unsigned int key); + +/* Get the first entry in the table (with the smallest `key`). + * Returns FALSE if the table is empty. */ +bool Curl_uint_tbl_first(struct uint_tbl *tbl, + unsigned int *pkey, void **pentry); + +/* Get the next key in the table, following `last_key` in natural order. + * Put another way, this is the smallest key greater than `last_key` in + * the table. `last_key` does not have to be present in the table. + * + * Returns FALSE when no such entry is in the table. + * + * This allows to iterate the table while being modified: + * - added keys higher than 'last_key' will be picked up by the iteration. + * - added keys lower than 'last_key' will not show up. + * - removed keys lower or equal to 'last_key' will not show up. + * - removed keys higher than 'last_key' will not be visited. */ +bool Curl_uint_tbl_next(struct uint_tbl *tbl, unsigned int last_key, + unsigned int *pkey, void **pentry); + +#endif /* HEADER_CURL_UINT_TABLE_H */ diff --git a/lib/url.c b/lib/url.c index efc79ccd11..ba62b53328 100644 --- a/lib/url.c +++ b/lib/url.c @@ -516,6 +516,15 @@ CURLcode Curl_open(struct Curl_easy **curl) } data->magic = CURLEASY_MAGIC_NUMBER; + /* most recent connection is not yet defined */ + data->state.lastconnect_id = -1; + data->state.recent_conn_id = -1; + /* and not assigned an id yet */ + data->id = -1; + data->mid = UINT_MAX; + data->master_mid = UINT_MAX; + data->progress.flags |= PGRS_HIDE; + data->state.current_speed = -1; /* init to negative == impossible */ Curl_hash_init(&data->meta_hash, 23, Curl_hash_str, Curl_str_key_compare, easy_meta_freeentry); @@ -528,26 +537,13 @@ CURLcode Curl_open(struct Curl_easy **curl) Curl_netrc_init(&data->state.netrc); result = Curl_init_userdefined(data); - if(result) - goto out; - - /* most recent connection is not yet defined */ - data->state.lastconnect_id = -1; - data->state.recent_conn_id = -1; - /* and not assigned an id yet */ - data->id = -1; - data->mid = -1; - data->master_mid = -1; - data->progress.flags |= PGRS_HIDE; - data->state.current_speed = -1; /* init to negative == impossible */ - -out: if(result) { Curl_dyn_free(&data->state.headerb); Curl_freeset(data); Curl_req_free(&data->req, data); Curl_hash_destroy(&data->meta_hash); + data->magic = 0; free(data); data = NULL; } @@ -599,6 +595,7 @@ void Curl_conn_free(struct Curl_easy *data, struct connectdata *conn) Curl_safefree(conn->unix_domain_socket); #endif Curl_safefree(conn->destination); + Curl_uint_spbset_destroy(&conn->xfers_attached); free(conn); /* free all the connection oriented data */ } @@ -891,10 +888,19 @@ static bool url_match_conn(struct connectdata *conn, void *userdata) return FALSE; else { /* transfer and conn multiplex. Are they on the same multi? */ - struct Curl_llist_node *e = Curl_llist_head(&conn->easyq); - struct Curl_easy *entry = Curl_node_elem(e); - if(entry->multi != data->multi) + unsigned int mid; + if(Curl_uint_spbset_first(&conn->xfers_attached, &mid)) { + struct Curl_easy *entry = Curl_multi_get_easy(data->multi, mid); + DEBUGASSERT(entry); + if(!entry || (entry->multi != data->multi)) + return FALSE; + } + else { + /* Since CONN_INUSE() checks the bitset, we SHOULD find a first + * mid in there. */ + DEBUGASSERT(0); return FALSE; + } } } /* `conn` is connected and we could add the transfer to it, if @@ -1156,16 +1162,16 @@ static bool url_match_conn(struct connectdata *conn, void *userdata) DEBUGASSERT(match->may_multiplex); DEBUGASSERT(conn->bits.multiplex); /* If multiplexed, make sure we do not go over concurrency limit */ - if(CONN_INUSE(conn) >= + if(CONN_ATTACHED(conn) >= Curl_multi_max_concurrent_streams(data->multi)) { infof(data, "client side MAX_CONCURRENT_STREAMS reached" - ", skip (%zu)", CONN_INUSE(conn)); + ", skip (%u)", CONN_ATTACHED(conn)); return FALSE; } - if(CONN_INUSE(conn) >= + if(CONN_ATTACHED(conn) >= Curl_conn_get_max_concurrent(data, conn, FIRSTSOCKET)) { - infof(data, "MAX_CONCURRENT_STREAMS reached, skip (%zu)", - CONN_INUSE(conn)); + infof(data, "MAX_CONCURRENT_STREAMS reached, skip (%u)", + CONN_ATTACHED(conn)); return FALSE; } /* When not multiplexed, we have a match here! */ @@ -1350,8 +1356,8 @@ static struct connectdata *allocate_conn(struct Curl_easy *data) conn->connect_only = data->set.connect_only; conn->transport = TRNSPRT_TCP; /* most of them are TCP streams */ - /* Initialize the easy handle list */ - Curl_llist_init(&conn->easyq, NULL); + /* Initialize the attached xfers bitset */ + Curl_uint_spbset_init(&conn->xfers_attached); #ifdef HAVE_GSSAPI conn->data_prot = PROT_CLEAR; @@ -3621,7 +3627,7 @@ static CURLcode create_conn(struct Curl_easy *data, connections_available = FALSE; break; case CPOOL_LIMIT_TOTAL: - if(data->master_mid >= 0) + if(data->master_mid != UINT_MAX) CURL_TRC_M(data, "Allowing sub-requests (like DoH) to override " "max connection limit"); else { @@ -3772,7 +3778,7 @@ CURLcode Curl_connect(struct Curl_easy *data, result = create_conn(data, &conn, asyncp); if(!result) { - if(CONN_INUSE(conn) > 1) + if(CONN_ATTACHED(conn) > 1) /* multiplexed */ *protocol_done = TRUE; else if(!*asyncp) { diff --git a/lib/urldata.h b/lib/urldata.h index 58cdb6023b..591e166cc8 100644 --- a/lib/urldata.h +++ b/lib/urldata.h @@ -742,7 +742,8 @@ struct connectdata { handle is still used by one or more easy handles and can only used by any other easy handle without careful consideration (== only for multiplexing) and it cannot be used by another multi handle! */ -#define CONN_INUSE(c) Curl_llist_count(&(c)->easyq) +#define CONN_INUSE(c) (!Curl_uint_spbset_empty(&(c)->xfers_attached)) +#define CONN_ATTACHED(c) Curl_uint_spbset_count(&(c)->xfers_attached) /**** Fields set when inited and not modified again */ curl_off_t connection_id; /* Contains a unique number to make it easier to @@ -829,7 +830,7 @@ struct connectdata { struct kerberos5data krb5; /* variables into the structure definition, */ #endif /* however, some of them are ftp specific. */ - struct Curl_llist easyq; /* List of easy handles using this connection */ + struct uint_spbset xfers_attached; /* mids of attached transfers */ /*************** Request - specific items ************/ #if defined(USE_WINDOWS_SSPI) && defined(SECPKG_ATTR_ENDPOINT_BINDINGS) @@ -1840,13 +1841,11 @@ struct Curl_easy { /* once an easy handle is added to a multi, either explicitly by the * libcurl application or implicitly during `curl_easy_perform()`, * a unique identifier inside this one multi instance. */ - curl_off_t mid; - curl_off_t master_mid; /* if set, this transfer belongs to a master */ + unsigned int mid; + unsigned int master_mid; /* if set, this transfer belongs to a master */ multi_sub_xfer_done_cb *sub_xfer_done; struct connectdata *conn; - struct Curl_llist_node multi_queue; /* for multihandle list management */ - struct Curl_llist_node conn_queue; /* list per connectdata */ CURLMstate mstate; /* the handle's state */ CURLcode result; /* previous result */ diff --git a/lib/vquic/curl_msh3.c b/lib/vquic/curl_msh3.c index d473b3a19f..53cfc03ae3 100644 --- a/lib/vquic/curl_msh3.c +++ b/lib/vquic/curl_msh3.c @@ -120,7 +120,7 @@ struct cf_msh3_ctx { struct cf_call_data call_data; struct curltime connect_started; /* time the current attempt started */ struct curltime handshake_at; /* time connect handshake finished */ - struct Curl_hash_offt streams; /* hash `data->mid` to `stream_ctx` */ + struct uint_hash streams; /* hash `data->mid` to `stream_ctx` */ /* Flags written by msh3/msquic thread */ bool handshake_complete; bool handshake_succeeded; @@ -131,7 +131,7 @@ struct cf_msh3_ctx { BIT(active); }; -static void h3_stream_hash_free(curl_off_t id, void *stream); +static void h3_stream_hash_free(unsigned int id, void *stream); static CURLcode cf_msh3_ctx_init(struct cf_msh3_ctx *ctx, const struct Curl_addrinfo *ai) @@ -139,7 +139,7 @@ static CURLcode cf_msh3_ctx_init(struct cf_msh3_ctx *ctx, CURLcode result; DEBUGASSERT(!ctx->initialized); - Curl_hash_offt_init(&ctx->streams, 63, h3_stream_hash_free); + Curl_uint_hash_init(&ctx->streams, 63, h3_stream_hash_free); result = Curl_sock_assign_addr(&ctx->addr, ai, TRNSPRT_QUIC); if(result) @@ -155,7 +155,7 @@ static CURLcode cf_msh3_ctx_init(struct cf_msh3_ctx *ctx, static void cf_msh3_ctx_free(struct cf_msh3_ctx *ctx) { if(ctx && ctx->initialized) { - Curl_hash_offt_destroy(&ctx->streams); + Curl_uint_hash_destroy(&ctx->streams); } free(ctx); } @@ -189,7 +189,7 @@ struct stream_ctx { }; #define H3_STREAM_CTX(ctx,data) ((struct stream_ctx *)((data && ctx)? \ - Curl_hash_offt_get(&(ctx)->streams, (data)->mid) : NULL)) + Curl_uint_hash_get(&(ctx)->streams, (data)->mid) : NULL)) static void h3_stream_ctx_free(struct stream_ctx *stream) { @@ -197,7 +197,7 @@ static void h3_stream_ctx_free(struct stream_ctx *stream) free(stream); } -static void h3_stream_hash_free(curl_off_t id, void *stream) +static void h3_stream_hash_free(unsigned int id, void *stream) { (void)id; DEBUGASSERT(stream); @@ -223,7 +223,7 @@ static CURLcode h3_data_setup(struct Curl_cfilter *cf, H3_STREAM_RECV_CHUNKS, BUFQ_OPT_SOFT_LIMIT); CURL_TRC_CF(data, cf, "data setup"); - if(!Curl_hash_offt_set(&ctx->streams, data->mid, stream)) { + if(!Curl_uint_hash_set(&ctx->streams, data->mid, stream)) { h3_stream_ctx_free(stream); return CURLE_OUT_OF_MEMORY; } @@ -239,7 +239,7 @@ static void h3_data_done(struct Curl_cfilter *cf, struct Curl_easy *data) (void)cf; if(stream) { CURL_TRC_CF(data, cf, "easy handle is done"); - Curl_hash_offt_remove(&ctx->streams, data->mid); + Curl_uint_hash_remove(&ctx->streams, data->mid); } } diff --git a/lib/vquic/curl_ngtcp2.c b/lib/vquic/curl_ngtcp2.c index c9d41f5a83..9269323d17 100644 --- a/lib/vquic/curl_ngtcp2.c +++ b/lib/vquic/curl_ngtcp2.c @@ -138,7 +138,7 @@ struct cf_ngtcp2_ctx { struct curltime handshake_at; /* time connect handshake finished */ struct bufc_pool stream_bufcp; /* chunk pool for streams */ struct dynbuf scratch; /* temp buffer for header construction */ - struct Curl_hash_offt streams; /* hash `data->mid` to `h3_stream_ctx` */ + struct uint_hash streams; /* hash `data->mid` to `h3_stream_ctx` */ size_t max_stream_window; /* max flow window for one stream */ uint64_t max_idle_ms; /* max idle time for QUIC connection */ uint64_t used_bidi_streams; /* bidi streams we have opened */ @@ -161,7 +161,7 @@ struct cf_ngtcp2_ctx { #define CF_CTX_CALL_DATA(cf) \ ((struct cf_ngtcp2_ctx *)(cf)->ctx)->call_data -static void h3_stream_hash_free(curl_off_t id, void *stream); +static void h3_stream_hash_free(unsigned int id, void *stream); static void cf_ngtcp2_ctx_init(struct cf_ngtcp2_ctx *ctx) { @@ -173,7 +173,7 @@ static void cf_ngtcp2_ctx_init(struct cf_ngtcp2_ctx *ctx) Curl_bufcp_init(&ctx->stream_bufcp, H3_STREAM_CHUNK_SIZE, H3_STREAM_POOL_SPARES); Curl_dyn_init(&ctx->scratch, CURL_MAX_HTTP_HEADER); - Curl_hash_offt_init(&ctx->streams, 63, h3_stream_hash_free); + Curl_uint_hash_init(&ctx->streams, 63, h3_stream_hash_free); ctx->initialized = TRUE; } @@ -184,7 +184,7 @@ static void cf_ngtcp2_ctx_free(struct cf_ngtcp2_ctx *ctx) vquic_ctx_free(&ctx->q); Curl_bufcp_free(&ctx->stream_bufcp); Curl_dyn_free(&ctx->scratch); - Curl_hash_offt_destroy(&ctx->streams); + Curl_uint_hash_destroy(&ctx->streams); Curl_ssl_peer_cleanup(&ctx->peer); } free(ctx); @@ -218,9 +218,7 @@ struct h3_stream_ctx { }; #define H3_STREAM_CTX(ctx,data) ((struct h3_stream_ctx *)(\ - data? Curl_hash_offt_get(&(ctx)->streams, (data)->mid) : NULL)) -#define H3_STREAM_CTX_ID(ctx,id) ((struct h3_stream_ctx *)(\ - Curl_hash_offt_get(&(ctx)->streams, (id)))) + data? Curl_uint_hash_get(&(ctx)->streams, (data)->mid) : NULL)) static void h3_stream_ctx_free(struct h3_stream_ctx *stream) { @@ -229,7 +227,7 @@ static void h3_stream_ctx_free(struct h3_stream_ctx *stream) free(stream); } -static void h3_stream_hash_free(curl_off_t id, void *stream) +static void h3_stream_hash_free(unsigned int id, void *stream) { (void)id; DEBUGASSERT(stream); @@ -259,7 +257,7 @@ static CURLcode h3_data_setup(struct Curl_cfilter *cf, stream->sendbuf_len_in_flight = 0; Curl_h1_req_parse_init(&stream->h1, H1_PARSE_DEFAULT_MAX_LINE_LEN); - if(!Curl_hash_offt_set(&ctx->streams, data->mid, stream)) { + if(!Curl_uint_hash_set(&ctx->streams, data->mid, stream)) { h3_stream_ctx_free(stream); return CURLE_OUT_OF_MEMORY; } @@ -298,7 +296,7 @@ static void h3_data_done(struct Curl_cfilter *cf, struct Curl_easy *data) CURL_TRC_CF(data, cf, "[%" FMT_PRId64 "] easy handle is done", stream->id); cf_ngtcp2_stream_close(cf, data, stream); - Curl_hash_offt_remove(&ctx->streams, data->mid); + Curl_uint_hash_remove(&ctx->streams, data->mid); } } @@ -551,7 +549,7 @@ static int cb_recv_stream_data(ngtcp2_conn *tconn, uint32_t flags, CURL_TRC_CF(data, cf, "[%" FMT_PRId64 "] read_stream(len=%zu) -> %zd", stream_id, buflen, nconsumed); if(nconsumed < 0) { - struct h3_stream_ctx *stream = H3_STREAM_CTX_ID(ctx, stream_id); + struct h3_stream_ctx *stream = H3_STREAM_CTX(ctx, data); if(data && stream) { CURL_TRC_CF(data, cf, "[%" FMT_PRId64 "] error on known stream, " "reset=%d, closed=%d", @@ -2617,7 +2615,7 @@ static CURLcode cf_ngtcp2_query(struct Curl_cfilter *cf, } else if(ctx->max_bidi_streams) { uint64_t avail_bidi_streams = 0; - uint64_t max_streams = CONN_INUSE(cf->conn); + uint64_t max_streams = CONN_ATTACHED(cf->conn); if(ctx->max_bidi_streams > ctx->used_bidi_streams) avail_bidi_streams = ctx->max_bidi_streams - ctx->used_bidi_streams; max_streams += avail_bidi_streams; @@ -2626,8 +2624,8 @@ static CURLcode cf_ngtcp2_query(struct Curl_cfilter *cf, else /* transport params not arrived yet? take our default. */ *pres1 = (int)Curl_multi_max_concurrent_streams(data->multi); CURL_TRC_CF(data, cf, "query conn[%" FMT_OFF_T "]: " - "MAX_CONCURRENT -> %d (%zu in use)", - cf->conn->connection_id, *pres1, CONN_INUSE(cf->conn)); + "MAX_CONCURRENT -> %d (%u in use)", + cf->conn->connection_id, *pres1, CONN_ATTACHED(cf->conn)); CF_DATA_RESTORE(cf, save); return CURLE_OK; } diff --git a/lib/vquic/curl_osslq.c b/lib/vquic/curl_osslq.c index e7c215ccf2..1065bb2284 100644 --- a/lib/vquic/curl_osslq.c +++ b/lib/vquic/curl_osslq.c @@ -285,7 +285,7 @@ struct cf_osslq_ctx { struct curltime handshake_at; /* time connect handshake finished */ struct curltime first_byte_at; /* when first byte was recvd */ struct bufc_pool stream_bufcp; /* chunk pool for streams */ - struct Curl_hash_offt streams; /* hash `data->mid` to `h3_stream_ctx` */ + struct uint_hash streams; /* hash `data->mid` to `h3_stream_ctx` */ size_t max_stream_window; /* max flow window for one stream */ uint64_t max_idle_ms; /* max idle time for QUIC connection */ SSL_POLL_ITEM *poll_items; /* Array for polling on writable state */ @@ -299,14 +299,14 @@ struct cf_osslq_ctx { BIT(need_send); /* QUIC connection needs to send */ }; -static void h3_stream_hash_free(curl_off_t id, void *stream); +static void h3_stream_hash_free(unsigned int id, void *stream); static void cf_osslq_ctx_init(struct cf_osslq_ctx *ctx) { DEBUGASSERT(!ctx->initialized); Curl_bufcp_init(&ctx->stream_bufcp, H3_STREAM_CHUNK_SIZE, H3_STREAM_POOL_SPARES); - Curl_hash_offt_init(&ctx->streams, 63, h3_stream_hash_free); + Curl_uint_hash_init(&ctx->streams, 63, h3_stream_hash_free); ctx->poll_items = NULL; ctx->curl_items = NULL; ctx->items_max = 0; @@ -317,7 +317,7 @@ static void cf_osslq_ctx_free(struct cf_osslq_ctx *ctx) { if(ctx && ctx->initialized) { Curl_bufcp_free(&ctx->stream_bufcp); - Curl_hash_offt_destroy(&ctx->streams); + Curl_uint_hash_destroy(&ctx->streams); Curl_ssl_peer_cleanup(&ctx->peer); free(ctx->poll_items); free(ctx->curl_items); @@ -591,7 +591,7 @@ struct h3_stream_ctx { }; #define H3_STREAM_CTX(ctx,data) ((struct h3_stream_ctx *)(\ - data? Curl_hash_offt_get(&(ctx)->streams, (data)->mid) : NULL)) + data? Curl_uint_hash_get(&(ctx)->streams, (data)->mid) : NULL)) static void h3_stream_ctx_free(struct h3_stream_ctx *stream) { @@ -602,7 +602,7 @@ static void h3_stream_ctx_free(struct h3_stream_ctx *stream) free(stream); } -static void h3_stream_hash_free(curl_off_t id, void *stream) +static void h3_stream_hash_free(unsigned int id, void *stream) { (void)id; DEBUGASSERT(stream); @@ -637,7 +637,7 @@ static CURLcode h3_data_setup(struct Curl_cfilter *cf, stream->recv_buf_nonflow = 0; Curl_h1_req_parse_init(&stream->h1, H1_PARSE_DEFAULT_MAX_LINE_LEN); - if(!Curl_hash_offt_set(&ctx->streams, data->mid, stream)) { + if(!Curl_uint_hash_set(&ctx->streams, data->mid, stream)) { h3_stream_ctx_free(stream); return CURLE_OUT_OF_MEMORY; } @@ -662,7 +662,7 @@ static void h3_data_done(struct Curl_cfilter *cf, struct Curl_easy *data) stream->closed = TRUE; } - Curl_hash_offt_remove(&ctx->streams, data->mid); + Curl_uint_hash_remove(&ctx->streams, data->mid); } } @@ -671,7 +671,7 @@ struct cf_ossq_find_ctx { struct h3_stream_ctx *stream; }; -static bool cf_osslq_find_stream(curl_off_t mid, void *val, void *user_data) +static bool cf_osslq_find_stream(unsigned int mid, void *val, void *user_data) { struct h3_stream_ctx *stream = val; struct cf_ossq_find_ctx *fctx = user_data; @@ -707,7 +707,7 @@ static struct cf_osslq_stream *cf_osslq_get_qstream(struct Curl_cfilter *cf, struct cf_ossq_find_ctx fctx; fctx.stream_id = stream_id; fctx.stream = NULL; - Curl_hash_offt_visit(&ctx->streams, cf_osslq_find_stream, &fctx); + Curl_uint_hash_visit(&ctx->streams, cf_osslq_find_stream, &fctx); if(fctx.stream) return &fctx.stream->s; } @@ -1420,14 +1420,14 @@ struct cf_ossq_recv_ctx { CURLcode result; }; -static bool cf_osslq_iter_recv(curl_off_t mid, void *val, void *user_data) +static bool cf_osslq_iter_recv(unsigned int mid, void *val, void *user_data) { struct h3_stream_ctx *stream = val; struct cf_ossq_recv_ctx *rctx = user_data; (void)mid; if(stream && !stream->closed && !Curl_bufq_is_full(&stream->recvbuf)) { - struct Curl_easy *sdata = Curl_multi_get_handle(rctx->multi, mid); + struct Curl_easy *sdata = Curl_multi_get_easy(rctx->multi, mid); if(sdata) { rctx->result = cf_osslq_stream_recv(&stream->s, rctx->cf, sdata); if(rctx->result) @@ -1479,7 +1479,7 @@ static CURLcode cf_progress_ingress(struct Curl_cfilter *cf, rctx.cf = cf; rctx.multi = data->multi; rctx.result = CURLE_OK; - Curl_hash_offt_visit(&ctx->streams, cf_osslq_iter_recv, &rctx); + Curl_uint_hash_visit(&ctx->streams, cf_osslq_iter_recv, &rctx); result = rctx.result; } @@ -1494,7 +1494,7 @@ struct cf_ossq_fill_ctx { size_t n; }; -static bool cf_osslq_collect_block_send(curl_off_t mid, void *val, +static bool cf_osslq_collect_block_send(unsigned int mid, void *val, void *user_data) { struct h3_stream_ctx *stream = val; @@ -1505,7 +1505,7 @@ static bool cf_osslq_collect_block_send(curl_off_t mid, void *val, return FALSE; if(stream && stream->s.ssl && stream->s.send_blocked) { - struct Curl_easy *sdata = Curl_multi_get_handle(fctx->multi, mid); + struct Curl_easy *sdata = Curl_multi_get_easy(fctx->multi, mid); fprintf(stderr, "[OSSLQ] stream %" FMT_PRId64 " sdata=%p\n", stream->s.id, (void *)sdata); if(sdata) { @@ -1534,8 +1534,8 @@ static CURLcode cf_osslq_check_and_unblock(struct Curl_cfilter *cf, if(ctx->h3.conn) { struct cf_ossq_fill_ctx fill_ctx; - if(ctx->items_max < Curl_hash_offt_count(&ctx->streams)) { - size_t nmax = Curl_hash_offt_count(&ctx->streams); + if(ctx->items_max < Curl_uint_hash_count(&ctx->streams)) { + size_t nmax = Curl_uint_hash_count(&ctx->streams); ctx->items_max = 0; tmpptr = realloc(ctx->poll_items, nmax * sizeof(SSL_POLL_ITEM)); if(!tmpptr) { @@ -1560,7 +1560,7 @@ static CURLcode cf_osslq_check_and_unblock(struct Curl_cfilter *cf, fill_ctx.ctx = ctx; fill_ctx.multi = data->multi; fill_ctx.n = 0; - Curl_hash_offt_visit(&ctx->streams, cf_osslq_collect_block_send, + Curl_uint_hash_visit(&ctx->streams, cf_osslq_collect_block_send, &fill_ctx); poll_count = fill_ctx.n; if(poll_count) { @@ -2378,7 +2378,7 @@ static CURLcode cf_osslq_query(struct Curl_cfilter *cf, return CURLE_HTTP3; } /* we report avail + in_use */ - v += CONN_INUSE(cf->conn); + v += CONN_ATTACHED(cf->conn); *pres1 = (v > INT_MAX) ? INT_MAX : (int)v; #else *pres1 = 100; diff --git a/lib/vquic/curl_quiche.c b/lib/vquic/curl_quiche.c index d48f783026..f2b96d733d 100644 --- a/lib/vquic/curl_quiche.c +++ b/lib/vquic/curl_quiche.c @@ -97,7 +97,7 @@ struct cf_quiche_ctx { struct curltime started_at; /* time the current attempt started */ struct curltime handshake_at; /* time connect handshake finished */ struct bufc_pool stream_bufcp; /* chunk pool for streams */ - struct Curl_hash_offt streams; /* hash `data->mid` to `stream_ctx` */ + struct uint_hash streams; /* hash `data->mid` to `stream_ctx` */ curl_off_t data_recvd; BIT(initialized); BIT(goaway); /* got GOAWAY from server */ @@ -115,7 +115,7 @@ static void quiche_debug_log(const char *line, void *argp) } #endif -static void h3_stream_hash_free(curl_off_t id, void *stream); +static void h3_stream_hash_free(unsigned int id, void *stream); static void cf_quiche_ctx_init(struct cf_quiche_ctx *ctx) { @@ -128,7 +128,7 @@ static void cf_quiche_ctx_init(struct cf_quiche_ctx *ctx) #endif Curl_bufcp_init(&ctx->stream_bufcp, H3_STREAM_CHUNK_SIZE, H3_STREAM_POOL_SPARES); - Curl_hash_offt_init(&ctx->streams, 63, h3_stream_hash_free); + Curl_uint_hash_init(&ctx->streams, 63, h3_stream_hash_free); ctx->data_recvd = 0; ctx->initialized = TRUE; } @@ -142,7 +142,7 @@ static void cf_quiche_ctx_free(struct cf_quiche_ctx *ctx) Curl_ssl_peer_cleanup(&ctx->peer); vquic_ctx_free(&ctx->q); Curl_bufcp_free(&ctx->stream_bufcp); - Curl_hash_offt_destroy(&ctx->streams); + Curl_uint_hash_destroy(&ctx->streams); } free(ctx); } @@ -180,7 +180,7 @@ struct stream_ctx { }; #define H3_STREAM_CTX(ctx,data) ((struct stream_ctx *)(\ - data? Curl_hash_offt_get(&(ctx)->streams, (data)->mid) : NULL)) + data? Curl_uint_hash_get(&(ctx)->streams, (data)->mid) : NULL)) static void h3_stream_ctx_free(struct stream_ctx *stream) { @@ -189,7 +189,7 @@ static void h3_stream_ctx_free(struct stream_ctx *stream) free(stream); } -static void h3_stream_hash_free(curl_off_t id, void *stream) +static void h3_stream_hash_free(unsigned int id, void *stream) { (void)id; DEBUGASSERT(stream); @@ -208,11 +208,11 @@ struct cf_quiche_visit_ctx { void *user_data; }; -static bool cf_quiche_stream_do(curl_off_t mid, void *val, void *user_data) +static bool cf_quiche_stream_do(unsigned int mid, void *val, void *user_data) { struct cf_quiche_visit_ctx *vctx = user_data; struct stream_ctx *stream = val; - struct Curl_easy *sdata = Curl_multi_get_handle(vctx->multi, mid); + struct Curl_easy *sdata = Curl_multi_get_easy(vctx->multi, mid); if(sdata) return vctx->cb(vctx->cf, sdata, stream, vctx->user_data); return TRUE; @@ -229,7 +229,7 @@ static void cf_quiche_for_all_streams(struct Curl_cfilter *cf, vctx.multi = multi; vctx.cb = do_cb; vctx.user_data = user_data; - Curl_hash_offt_visit(&ctx->streams, cf_quiche_stream_do, &vctx); + Curl_uint_hash_visit(&ctx->streams, cf_quiche_stream_do, &vctx); } static bool cf_quiche_do_resume(struct Curl_cfilter *cf, @@ -276,7 +276,7 @@ static CURLcode h3_data_setup(struct Curl_cfilter *cf, H3_STREAM_RECV_CHUNKS, BUFQ_OPT_SOFT_LIMIT); Curl_h1_req_parse_init(&stream->h1, H1_PARSE_DEFAULT_MAX_LINE_LEN); - if(!Curl_hash_offt_set(&ctx->streams, data->mid, stream)) { + if(!Curl_uint_hash_set(&ctx->streams, data->mid, stream)) { h3_stream_ctx_free(stream); return CURLE_OUT_OF_MEMORY; } @@ -306,7 +306,7 @@ static void h3_data_done(struct Curl_cfilter *cf, struct Curl_easy *data) if(result) CURL_TRC_CF(data, cf, "data_done, flush egress -> %d", result); } - Curl_hash_offt_remove(&ctx->streams, data->mid); + Curl_uint_hash_remove(&ctx->streams, data->mid); } } @@ -581,13 +581,13 @@ struct cf_quich_disp_ctx { CURLcode result; }; -static bool cf_quiche_disp_event(curl_off_t mid, void *val, void *user_data) +static bool cf_quiche_disp_event(unsigned int mid, void *val, void *user_data) { struct cf_quich_disp_ctx *dctx = user_data; struct stream_ctx *stream = val; if(stream->id == dctx->stream_id) { - struct Curl_easy *sdata = Curl_multi_get_handle(dctx->multi, mid); + struct Curl_easy *sdata = Curl_multi_get_easy(dctx->multi, mid); if(sdata) dctx->result = cf_quiche_ev_process(dctx->cf, sdata, stream, dctx->ev); return FALSE; /* stop iterating */ @@ -630,7 +630,7 @@ static CURLcode cf_poll_events(struct Curl_cfilter *cf, else { /* another transfer, do not return errors, as they are not for * the calling transfer */ - Curl_hash_offt_visit(&ctx->streams, cf_quiche_disp_event, &dctx); + Curl_uint_hash_visit(&ctx->streams, cf_quiche_disp_event, &dctx); quiche_h3_event_free(ev); } } @@ -1572,14 +1572,14 @@ static CURLcode cf_quiche_query(struct Curl_cfilter *cf, switch(query) { case CF_QUERY_MAX_CONCURRENT: { - curl_uint64_t max_streams = CONN_INUSE(cf->conn); + curl_uint64_t max_streams = CONN_ATTACHED(cf->conn); if(!ctx->goaway) { max_streams += quiche_conn_peer_streams_left_bidi(ctx->qconn); } *pres1 = (max_streams > INT_MAX) ? INT_MAX : (int)max_streams; CURL_TRC_CF(data, cf, "query conn[%" FMT_OFF_T "]: " - "MAX_CONCURRENT -> %d (%zu in use)", - cf->conn->connection_id, *pres1, CONN_INUSE(cf->conn)); + "MAX_CONCURRENT -> %d (%u in use)", + cf->conn->connection_id, *pres1, CONN_ATTACHED(cf->conn)); return CURLE_OK; } case CF_QUERY_CONNECT_REPLY_MS: diff --git a/tests/data/Makefile.am b/tests/data/Makefile.am index 793501a38f..5193fc8102 100644 --- a/tests/data/Makefile.am +++ b/tests/data/Makefile.am @@ -276,6 +276,6 @@ test3032 \ test3100 test3101 test3102 test3103 test3104 test3105 \ \ test3200 test3201 test3202 test3203 test3204 test3205 test3207 test3208 \ -test3209 test3210 +test3209 test3210 test3211 test3212 test3213 EXTRA_DIST = $(TESTCASES) DISABLED diff --git a/tests/data/test3211 b/tests/data/test3211 new file mode 100644 index 0000000000..bc5c765b9b --- /dev/null +++ b/tests/data/test3211 @@ -0,0 +1,22 @@ + + + +unittest +uint_bset + + + +# +# Client-side + + +none + + +unittest + + +uint_bset unit tests + + + diff --git a/tests/data/test3212 b/tests/data/test3212 new file mode 100644 index 0000000000..bc5c765b9b --- /dev/null +++ b/tests/data/test3212 @@ -0,0 +1,22 @@ + + + +unittest +uint_bset + + + +# +# Client-side + + +none + + +unittest + + +uint_bset unit tests + + + diff --git a/tests/data/test3213 b/tests/data/test3213 new file mode 100644 index 0000000000..1eb1b9da4b --- /dev/null +++ b/tests/data/test3213 @@ -0,0 +1,22 @@ + + + +unittest +uint_spbset + + + +# +# Client-side + + +none + + +unittest + + +uint_spbset unit tests + + + diff --git a/tests/http/test_07_upload.py b/tests/http/test_07_upload.py index 438873e0ea..8b33325d34 100644 --- a/tests/http/test_07_upload.py +++ b/tests/http/test_07_upload.py @@ -549,7 +549,8 @@ class TestUpload: if r.exit_code == 18: # PARTIAL_FILE is always ok pass elif proto == 'h2': - r.check_exit_code(16) # CURLE_HTTP2 also ok + # CURLE_HTTP2, CURLE_HTTP2_STREAM + assert r.exit_code in [16, 92], f'unexpected exit code\n{r.dump_logs()}' elif proto == 'h3': r.check_exit_code(95) # CURLE_HTTP3 also ok else: diff --git a/tests/unit/Makefile.inc b/tests/unit/Makefile.inc index 6d0b296416..7d9f91df2c 100644 --- a/tests/unit/Makefile.inc +++ b/tests/unit/Makefile.inc @@ -43,7 +43,8 @@ UNITPROGS = unit1300 unit1302 unit1303 unit1304 unit1305 unit1307 \ unit1660 unit1661 unit1663 unit1664 \ unit2600 unit2601 unit2602 unit2603 unit2604 \ unit3200 \ - unit3205 + unit3205 \ + unit3211 unit3212 unit3213 unit1300_SOURCES = unit1300.c $(UNITFILES) @@ -146,3 +147,9 @@ unit2604_SOURCES = unit2604.c $(UNITFILES) unit3200_SOURCES = unit3200.c $(UNITFILES) unit3205_SOURCES = unit3205.c $(UNITFILES) + +unit3211_SOURCES = unit3211.c $(UNITFILES) + +unit3212_SOURCES = unit3212.c $(UNITFILES) + +unit3213_SOURCES = unit3213.c $(UNITFILES) diff --git a/tests/unit/unit3211.c b/tests/unit/unit3211.c new file mode 100644 index 0000000000..8bb23e73e7 --- /dev/null +++ b/tests/unit/unit3211.c @@ -0,0 +1,153 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curlcheck.h" + +#include "urldata.h" +#include "uint-bset.h" +#include "curl_trc.h" + +static CURLcode unit_setup(void) +{ + return CURLE_OK; +} + +static unsigned int s1[] = { /* spread numbers, some at slot edges */ + 0, 1, 4, 17, 63, 64, 65, 66, + 90, 99, +}; +static unsigned int s2[] = { /* set with all bits in slot1 set */ + 64, 65, 66, 67, 68, 69, 70, 71, + 72, 73, 74, 75, 76, 77, 78, 79, + 80, 81, 82, 83, 84, 85, 86, 87, + 88, 89, 90, 91, 92, 93, 94, 95, + 96, 97, 98, 99, 100, 101, 102, 103, + 104, 105, 106, 107, 108, 109, 110, 111, + 112, 113, 114, 115, 116, 117, 118, 119, + 120, 121, 122, 123, 124, 125, 126, 127, +}; + +static void check_set(const char *name, unsigned int capacity, + unsigned int *s, size_t slen) +{ + struct uint_bset bset; + size_t i, j; + unsigned int n, c; + + fprintf(stderr, "test %s, capacity=%u, %zu numbers\n", + name, capacity, slen); + Curl_uint_bset_init(&bset); + fail_unless(!Curl_uint_bset_resize(&bset, capacity), "bset resize failed"); + c = Curl_uint_bset_capacity(&bset); + fail_unless(c == (((capacity + 63) / 64) * 64), "wrong capacity"); + + Curl_uint_bset_clear(&bset); + c = Curl_uint_bset_count(&bset); + fail_unless(c == 0, "set count is not 0"); + + for(i = 0; i < slen; ++i) { /* add all */ + fail_unless(Curl_uint_bset_add(&bset, s[i]), "failed to add"); + for(j = i + 1; j < slen; ++j) + fail_unless(!Curl_uint_bset_contains(&bset, s[j]), "unexpectedly found"); + } + + for(i = 0; i < slen; ++i) { /* all present */ + fail_unless(Curl_uint_bset_contains(&bset, s[i]), "failed presence check"); + } + + /* iterator over all numbers */ + fail_unless(Curl_uint_bset_first(&bset, &n), "first failed"); + fail_unless(n == s[0], "first not correct number"); + for(i = 1; i < slen; ++i) { + fail_unless(Curl_uint_bset_next(&bset, n, &n), "next failed"); + if(n != s[i]) { + fprintf(stderr, "expected next to be %u, not %u\n", s[i], n); + fail_unless(n == s[i], "next not correct number"); + } + } + + /* Adding capacity number does not work (0 - capacity-1) */ + c = Curl_uint_bset_capacity(&bset); + fail_unless(!Curl_uint_bset_add(&bset, c), "add out of range worked"); + /* The count it correct */ + c = Curl_uint_bset_count(&bset); + fail_unless(c == slen, "set count is wrong"); + + for(i = 0; i < slen; i += 2) { /* remove every 2nd */ + Curl_uint_bset_remove(&bset, s[i]); + fail_unless(!Curl_uint_bset_contains(&bset, s[i]), "unexpectedly found"); + } + for(i = 1; i < slen; i += 2) { /* others still there */ + fail_unless(Curl_uint_bset_contains(&bset, s[i]), "unexpectedly gone"); + } + /* The count is half */ + c = Curl_uint_bset_count(&bset); + fail_unless(c == slen/2, "set count is wrong"); + + Curl_uint_bset_clear(&bset); + c = Curl_uint_bset_count(&bset); + fail_unless(c == 0, "set count is not 0"); + for(i = 0; i < slen; i++) { /* none present any longer */ + fail_unless(!Curl_uint_bset_contains(&bset, s[i]), "unexpectedly there"); + } + + for(i = 0; i < slen; ++i) { /* add all again */ + fail_unless(Curl_uint_bset_add(&bset, s[i]), "failed to add"); + } + + fail_unless(!Curl_uint_bset_resize(&bset, capacity * 2), + "resize double failed"); + for(i = 0; i < slen; i++) { /* all still present after resize */ + fail_unless(Curl_uint_bset_contains(&bset, s[i]), "unexpectedly lost"); + } + + fail_unless(!Curl_uint_bset_resize(&bset, capacity), "resize back failed"); + for(i = 0; i < slen; i++) /* all still present after resize back */ + fail_unless(Curl_uint_bset_contains(&bset, s[i]), "unexpectedly lost"); + + fail_unless(!Curl_uint_bset_resize(&bset, capacity/2), "resize half failed"); + /* halfed the size, what numbers remain in set? */ + c = Curl_uint_bset_capacity(&bset); + n = 0; + for(i = 0; i < slen; ++i) { + if(s[i] < c) + ++n; + } + fail_unless(n == Curl_uint_bset_count(&bset), "set count(halfed) wrong"); + for(i = 0; i < n; i++) /* still present after resize half */ + fail_unless(Curl_uint_bset_contains(&bset, s[i]), "unexpectedly lost"); + + Curl_uint_bset_destroy(&bset); +} + +static void unit_stop(void) +{ +} + + +UNITTEST_START + + check_set("s1", 100, s1, CURL_ARRAYSIZE(s1)); + check_set("s2", 1000, s2, CURL_ARRAYSIZE(s2)); + +UNITTEST_STOP diff --git a/tests/unit/unit3212.c b/tests/unit/unit3212.c new file mode 100644 index 0000000000..977dccfd4d --- /dev/null +++ b/tests/unit/unit3212.c @@ -0,0 +1,136 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curlcheck.h" + +#include "urldata.h" +#include "uint-table.h" +#include "curl_trc.h" + +#define TBL_SIZE 100 + +static struct uint_tbl tbl; + +static int dummy; + +static CURLcode unit_setup(void) +{ + Curl_uint_tbl_init(&tbl, NULL); + return Curl_uint_tbl_resize(&tbl, TBL_SIZE); +} + +static void unit_stop(void) +{ + Curl_uint_tbl_destroy(&tbl); +} + +static void check3212(void) +{ + unsigned int i, key, n; + void *entry; + + fail_unless(Curl_uint_tbl_capacity(&tbl) == TBL_SIZE, "wrong capacity"); + + for(i = 0; i < TBL_SIZE; ++i) { + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add"); + fail_unless(key == i, "unexpected key assigned"); + } + /* table should be full now */ + fail_unless(Curl_uint_tbl_count(&tbl) == TBL_SIZE, "wrong count"); + fail_unless(!Curl_uint_tbl_add(&tbl, &dummy, &key), "could add more"); + /* remove every 2nd entry, from full table */ + n = TBL_SIZE; + for(i = 0; i < TBL_SIZE; i += 2) { + Curl_uint_tbl_remove(&tbl, i); + --n; + fail_unless(Curl_uint_tbl_count(&tbl) == n, "wrong count after remove"); + } + /* remove same again, should not change count */ + for(i = 0; i < TBL_SIZE; i += 2) { + Curl_uint_tbl_remove(&tbl, i); + fail_unless(Curl_uint_tbl_count(&tbl) == n, "wrong count after remove"); + } + /* still contains all odd entries */ + for(i = 1; i < TBL_SIZE; i += 2) { + fail_unless(Curl_uint_tbl_contains(&tbl, i), "does not contain"); + fail_unless(Curl_uint_tbl_get(&tbl, i) == &dummy, + "does not contain dummy"); + } + /* get the first key */ + fail_unless(Curl_uint_tbl_first(&tbl, &key, &entry), "first failed"); + fail_unless(key == 1, "unexpected first key"); + fail_unless(entry == &dummy, "unexpected first entry"); + /* get the second key */ + fail_unless(Curl_uint_tbl_next(&tbl, 1, &key, &entry), "next1 failed"); + fail_unless(key == 3, "unexpected second key"); + fail_unless(entry == &dummy, "unexpected second entry"); + /* get the key after 42 */ + fail_unless(Curl_uint_tbl_next(&tbl, 42, &key, &entry), "next42 failed"); + fail_unless(key == 43, "unexpected next42 key"); + fail_unless(entry == &dummy, "unexpected next42 entry"); + + /* double capacity */ + n = Curl_uint_tbl_count(&tbl); + fail_unless(!Curl_uint_tbl_resize(&tbl, TBL_SIZE * 2), + "error doubling size"); + fail_unless(Curl_uint_tbl_count(&tbl) == n, "wrong resize count"); + /* resize to half of original */ + fail_unless(!Curl_uint_tbl_resize(&tbl, TBL_SIZE / 2), "error halving size"); + fail_unless(Curl_uint_tbl_count(&tbl) == n / 2, "wrong half size count"); + for(i = 1; i < TBL_SIZE / 2; i += 2) { + fail_unless(Curl_uint_tbl_contains(&tbl, i), "does not contain"); + fail_unless(Curl_uint_tbl_get(&tbl, i) == &dummy, + "does not contain dummy"); + } + /* clear */ + Curl_uint_tbl_clear(&tbl); + fail_unless(!Curl_uint_tbl_count(&tbl), "count not 0 after clear"); + for(i = 0; i < TBL_SIZE / 2; ++i) { + fail_unless(!Curl_uint_tbl_contains(&tbl, i), "does contain, should not"); + } + /* add after clear gets key 0 again */ + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add"); + fail_unless(key == 0, "unexpected key assigned"); + /* remove it again and add, should get key 1 */ + Curl_uint_tbl_remove(&tbl, key); + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add"); + fail_unless(key == 1, "unexpected key assigned"); + /* clear, fill, remove one, add, should get the removed key again */ + Curl_uint_tbl_clear(&tbl); + for(i = 0; i < Curl_uint_tbl_capacity(&tbl); ++i) + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add"); + fail_unless(!Curl_uint_tbl_add(&tbl, &dummy, &key), "add on full"); + Curl_uint_tbl_remove(&tbl, 17); + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add again"); + fail_unless(key == 17, "unexpected key assigned"); + /* and again, triggering key search wrap around */ + Curl_uint_tbl_remove(&tbl, 17); + fail_unless(Curl_uint_tbl_add(&tbl, &dummy, &key), "failed to add again"); + fail_unless(key == 17, "unexpected key assigned"); +} + +UNITTEST_START + +check3212(); + +UNITTEST_STOP diff --git a/tests/unit/unit3213.c b/tests/unit/unit3213.c new file mode 100644 index 0000000000..f82e55637f --- /dev/null +++ b/tests/unit/unit3213.c @@ -0,0 +1,127 @@ +/*************************************************************************** + * _ _ ____ _ + * Project ___| | | | _ \| | + * / __| | | | |_) | | + * | (__| |_| | _ <| |___ + * \___|\___/|_| \_\_____| + * + * Copyright (C) Daniel Stenberg, , et al. + * + * This software is licensed as described in the file COPYING, which + * you should have received as part of this distribution. The terms + * are also available at https://curl.se/docs/copyright.html. + * + * You may opt to use, copy, modify, merge, publish, distribute and/or sell + * copies of the Software, and permit persons to whom the Software is + * furnished to do so, under the terms of the COPYING file. + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY + * KIND, either express or implied. + * + * SPDX-License-Identifier: curl + * + ***************************************************************************/ +#include "curlcheck.h" + +#include "urldata.h" +#include "uint-spbset.h" +#include "curl_trc.h" + +static CURLcode unit_setup(void) +{ + return CURLE_OK; +} + +static unsigned int s1_3213[] = { /* spread numbers, some at slot edges */ + 0, 1, 4, 17, 63, 64, 65, 66, + 90, 99, +}; +static unsigned int s2_3213[] = { /* set with all bits in slot1 set */ + 64, 65, 66, 67, 68, 69, 70, 71, + 72, 73, 74, 75, 76, 77, 78, 79, + 80, 81, 82, 83, 84, 85, 86, 87, + 88, 89, 90, 91, 92, 93, 94, 95, + 96, 97, 98, 99, 100, 101, 102, 103, + 104, 105, 106, 107, 108, 109, 110, 111, + 112, 113, 114, 115, 116, 117, 118, 119, + 120, 121, 122, 123, 124, 125, 126, 127, +}; +static unsigned int s3_3213[] = { /* very spread numbers */ + 2232, 5167, 8204, 8526, 8641, 10056, 10140, 10611, + 10998, 11626, 13735, 15539, 17947, 24295, 27833, 30318, +}; + +static void check_spbset(const char *name, unsigned int *s, size_t slen) +{ + struct uint_spbset bset; + size_t i, j; + unsigned int n, c; + + fprintf(stderr, "test %s, %zu numbers\n", name, slen); + + Curl_uint_spbset_init(&bset); + + Curl_uint_spbset_clear(&bset); + c = Curl_uint_spbset_count(&bset); + fail_unless(c == 0, "set count is not 0"); + + for(i = 0; i < slen; ++i) { /* add all */ + fail_unless(Curl_uint_spbset_add(&bset, s[i]), "failed to add"); + for(j = i + 1; j < slen; ++j) + fail_unless(!Curl_uint_spbset_contains(&bset, s[j]), + "unexpectedly found"); + } + + for(i = 0; i < slen; ++i) { /* all present */ + fail_unless(Curl_uint_spbset_contains(&bset, s[i]), + "failed presence check"); + } + + /* iterator over all numbers */ + fail_unless(Curl_uint_spbset_first(&bset, &n), "first failed"); + fail_unless(n == s[0], "first not correct number"); + for(i = 1; i < slen; ++i) { + fail_unless(Curl_uint_spbset_next(&bset, n, &n), "next failed"); + if(n != s[i]) { + fprintf(stderr, "expected next to be %u, not %u\n", s[i], n); + fail_unless(n == s[i], "next not correct number"); + } + } + + for(i = 0; i < slen; i += 2) { /* remove every 2nd */ + Curl_uint_spbset_remove(&bset, s[i]); + fail_unless(!Curl_uint_spbset_contains(&bset, s[i]), "unexpectedly found"); + } + for(i = 1; i < slen; i += 2) { /* others still there */ + fail_unless(Curl_uint_spbset_contains(&bset, s[i]), "unexpectedly gone"); + } + /* The count is half */ + c = Curl_uint_spbset_count(&bset); + fail_unless(c == slen/2, "set count is wrong"); + + Curl_uint_spbset_clear(&bset); + c = Curl_uint_spbset_count(&bset); + fail_unless(c == 0, "set count is not 0"); + for(i = 0; i < slen; i++) { /* none present any longer */ + fail_unless(!Curl_uint_spbset_contains(&bset, s[i]), "unexpectedly there"); + } + + for(i = 0; i < slen; ++i) { /* add all again */ + fail_unless(Curl_uint_spbset_add(&bset, s[i]), "failed to add"); + } + + Curl_uint_spbset_destroy(&bset); +} + +static void unit_stop(void) +{ +} + + +UNITTEST_START + + check_spbset("s1", s1_3213, CURL_ARRAYSIZE(s1_3213)); + check_spbset("s2", s2_3213, CURL_ARRAYSIZE(s2_3213)); + check_spbset("s3", s3_3213, CURL_ARRAYSIZE(s3_3213)); + +UNITTEST_STOP -- 2.47.2