From e80c893254ff3254188a708c9e37c44ae892ff39 Mon Sep 17 00:00:00 2001 From: Stefan Eissing Date: Tue, 24 Jun 2025 12:57:04 +0200 Subject: [PATCH] multi: xfer table/bitset, handle limits * calculate capacity growth on multi's xfer table and bitsets to work correctly when approaching UINT_MAX * uint-bset: track the first 64bit slot used. This avoids slot scans on empty sets. * uint-tbl: remove restriction to grow ot UINT_MAX, it is multi's job to enforce limits suitable for its use * test751: use curl_mfprintf() for error messages Closes #17731 --- lib/multi.c | 65 ++++++++++++++++++++++++++++-------------- lib/uint-bset.c | 17 +++++++---- lib/uint-bset.h | 1 + lib/uint-table.c | 4 +-- tests/libtest/lib751.c | 4 +-- 5 files changed, 61 insertions(+), 30 deletions(-) diff --git a/lib/multi.c b/lib/multi.c index 047fdc43f6..5377bc8d15 100644 --- a/lib/multi.c +++ b/lib/multi.c @@ -339,35 +339,58 @@ static void multi_warn_debug(struct Curl_multi *multi, struct Curl_easy *data) 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) * 64; - DEBUGASSERT(newsize > capacity); + unsigned int new_size = 0; + /* Prepare to make this into a CURLMOPT_MAX_TRANSFERS, because some + * applications may want to prevent a run-away of their memory use. */ + /* UINT_MAX is our "invalid" id, do not let the table grow up to that. */ + const unsigned int max_capacity = UINT_MAX - 1; + + if(capacity < max_capacity) { + /* 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 are quite memory efficient, + * regard less than 25% free as insufficient. + * (for low capacities, e.g. multi_easy, 4 or less). */ + unsigned int used = Curl_uint_tbl_count(&multi->xfers); + unsigned int unused = capacity - used; + unsigned int min_unused = CURLMAX(capacity >> 2, 4); + if(unused <= min_unused) { + /* Make sure the uint arithmetic here works on the corner + * cases where we are close to max_capacity or UINT_MAX */ + if((min_unused >= max_capacity) || + ((max_capacity - min_unused) <= capacity) || + ((UINT_MAX - min_unused - 63) <= capacity)) { + new_size = max_capacity; /* can not be larger than this */ + } + else { + /* make it a 64 multiple, since our bitsets frow by that and + * small (easy_multi) grows to at least 64 on first resize. */ + new_size = CURLMIN((((used + min_unused) + 63) / 64) * 64, + max_capacity); + } + } + } + + if(new_size > capacity) { /* 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->dirty, newsize) || - Curl_uint_bset_resize(&multi->pending, newsize) || - Curl_uint_bset_resize(&multi->msgsent, newsize) || - Curl_uint_tbl_resize(&multi->xfers, newsize)) + CURL_TRC_M(data, "increasing xfer table size to %u", new_size); + if(Curl_uint_bset_resize(&multi->process, new_size) || + Curl_uint_bset_resize(&multi->dirty, new_size) || + Curl_uint_bset_resize(&multi->pending, new_size) || + Curl_uint_bset_resize(&multi->msgsent, new_size) || + Curl_uint_tbl_resize(&multi->xfers, new_size)) 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 */ + + /* Insert the easy into the table now */ if(!Curl_uint_tbl_add(&multi->xfers, data, &data->mid)) { - DEBUGASSERT(0); + /* MUST only happen when table is full */ + DEBUGASSERT(Curl_uint_tbl_capacity(&multi->xfers) <= + Curl_uint_tbl_count(&multi->xfers)); return CURLM_OUT_OF_MEMORY; } return CURLM_OK; diff --git a/lib/uint-bset.c b/lib/uint-bset.c index 2086006180..b31409cebb 100644 --- a/lib/uint-bset.c +++ b/lib/uint-bset.c @@ -45,7 +45,8 @@ void Curl_uint_bset_init(struct uint_bset *bset) CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax) { - unsigned int nslots = (nmax + 63) / 64; + unsigned int nslots = (nmax < (UINT_MAX-63)) ? + ((nmax + 63) / 64) : (UINT_MAX / 64); DEBUGASSERT(bset->init == CURL_UINT_BSET_MAGIC); if(nslots != bset->nslots) { @@ -60,6 +61,7 @@ CURLcode Curl_uint_bset_resize(struct uint_bset *bset, unsigned int nmax) } bset->slots = slots; bset->nslots = nslots; + bset->first_slot_used = 0; } return CURLE_OK; } @@ -94,7 +96,7 @@ unsigned int Curl_uint_bset_count(struct uint_bset *bset) bool Curl_uint_bset_empty(struct uint_bset *bset) { unsigned int i; - for(i = 0; i < bset->nslots; ++i) { + for(i = bset->first_slot_used; i < bset->nslots; ++i) { if(bset->slots[i]) return FALSE; } @@ -104,8 +106,10 @@ bool Curl_uint_bset_empty(struct uint_bset *bset) void Curl_uint_bset_clear(struct uint_bset *bset) { - if(bset->nslots) + if(bset->nslots) { memset(bset->slots, 0, bset->nslots * sizeof(curl_uint64_t)); + bset->first_slot_used = UINT_MAX; + } } @@ -115,6 +119,8 @@ bool Curl_uint_bset_add(struct uint_bset *bset, unsigned int i) if(islot >= bset->nslots) return FALSE; bset->slots[islot] |= ((curl_uint64_t)1 << (i % 64)); + if(islot < bset->first_slot_used) + bset->first_slot_used = islot; return TRUE; } @@ -139,13 +145,14 @@ bool Curl_uint_bset_contains(struct uint_bset *bset, unsigned int i) bool Curl_uint_bset_first(struct uint_bset *bset, unsigned int *pfirst) { unsigned int i; - for(i = 0; i < bset->nslots; ++i) { + for(i = bset->first_slot_used; i < bset->nslots; ++i) { if(bset->slots[i]) { *pfirst = (i * 64) + CURL_CTZ64(bset->slots[i]); + bset->first_slot_used = i; return TRUE; } } - *pfirst = UINT_MAX; /* a value we cannot store */ + bset->first_slot_used = *pfirst = UINT_MAX; return FALSE; } diff --git a/lib/uint-bset.h b/lib/uint-bset.h index d998dccdfe..cc405cc656 100644 --- a/lib/uint-bset.h +++ b/lib/uint-bset.h @@ -42,6 +42,7 @@ struct uint_bset { curl_uint64_t *slots; unsigned int nslots; + unsigned int first_slot_used; #ifdef DEBUGBUILD int init; #endif diff --git a/lib/uint-table.c b/lib/uint-table.c index d8de1b128a..c235fc08bb 100644 --- a/lib/uint-table.c +++ b/lib/uint-table.c @@ -68,7 +68,7 @@ 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)) + if(!nrows) return CURLE_BAD_FUNCTION_ARGUMENT; if(nrows != tbl->nrows) { void **rows = calloc(nrows, sizeof(void *)); @@ -130,7 +130,7 @@ bool Curl_uint_tbl_add(struct uint_tbl *tbl, void *entry, unsigned int *pkey) DEBUGASSERT(tbl->init == CURL_UINT_TBL_MAGIC); if(!entry || !pkey) return FALSE; - *pkey = UINT_MAX; /* always invalid */ + *pkey = UINT_MAX; if(tbl->nentries == tbl->nrows) /* full */ return FALSE; diff --git a/tests/libtest/lib751.c b/tests/libtest/lib751.c index f9ebbf1fa8..bc8ddcfdcb 100644 --- a/tests/libtest/lib751.c +++ b/tests/libtest/lib751.c @@ -63,7 +63,7 @@ static CURLcode test_lib751(char *URL) mres = curl_multi_add_handle(m, e); if(mres != CURLM_OK) { - printf("MULTI ERROR: %s\n", curl_multi_strerror(mres)); + curl_mfprintf(stderr, "MULTI ERROR: %s\n", curl_multi_strerror(mres)); res = CURLE_FAILED_INIT; goto test_cleanup; } @@ -72,7 +72,7 @@ static CURLcode test_lib751(char *URL) test_cleanup: if(res) - printf("ERROR: %s\n", curl_easy_strerror(res)); + curl_mfprintf(stderr, "ERROR: %s\n", curl_easy_strerror(res)); for(i = 0; i < 1000; i++) { if(easies[i]) { -- 2.47.2