Yedidya Feldblum

uint_divisor, lifted from thrift Fast64BitRemainderCalculator Summary: Lift `apache::thrift::frozen::detail::Fast64BitRemainderCalculator` into a new public header `folly/math/Division.h` as `folly::uint_divisor<Word>`, generalized to all unsigned integer types. Uses Lemire's constant-divisor technique (credited in doc-comments). Key changes vs. the thrift original: - Support all unsigned integer types, possibly falling back to integer division. - Support zero divisors since the optimized algorithm does not perform division. - Calculates composite division and remainder, division, or remainder. - `constexpr` construction and invocation. - Invocable-object usage with `operator()` in addition to `divrem`. Mathematical operator usage with `operator/` and `operator%` in addition to `div` and `rem`. - Thrift uses Lemire’s direct fast-remainder algorithm: multiply by a precomputed reciprocal, then perform another widened multiply to recover the remainder. uint_divisor uses the same reciprocal to compute the exact quotient and derives the remainder as dividend - quotient * divisor. For 64-bit words this reduces the hot path from roughly four multiplies to three while remaining branchless. Narrow types retain Lemire’s direct remainder path where it benchmarks faster. - Hold the original divisor in addition to the computed multiplier to support mathematical operator usage. This increases in-situ object size. - Add `uint_divisor<Word>::calc` that does not hold the original divisor; let both `uint_divisor` and `Fast64BitRemainderCalculator` delegate to it. Reviewed By: iahs Differential Revision: D115907214 fbshipit-source-id: de6d55b8dac71489f4f36b382eeb9e065380cad1

folly/executors: throw instead of crashing on non-positive numPriorities Summary: `CPUThreadPoolExecutor(numThreads, numPriorities, ...)` is a public constructor overload, and a caller-supplied non-positive `numPriorities` reached three different `CHECK`-based crashes depending on which internal path handled it, all at construction time (cold, once-per-executor): - `CPUThreadPoolExecutor::makeLifoSemPriorityQueue` (used when `FLAGS_folly_cputhreadpoolexecutor_use_throttled_lifo_sem` is disabled) — `CHECK_GT(numPriorities, 0)`. - `PriorityLifoSemMPMCQueue`'s two constructors (used by the `numThreads, numPriorities, maxQueueSize` overload) — `CHECK_GT` on both the priority count and the capacities-range size, plus an upper-bound `CHECK_LT`. - `PriorityUnboundedBlockingQueue` (used by the *default* path, since `folly_cputhreadpoolexecutor_use_throttled_lifo_sem` defaults to `true`) had **no validation at all** — a non-positive `numPriorities` silently constructed a degenerate zero-priority queue instead of crashing or throwing, which `addWithPriority`'s priority-to-slot translation cannot handle correctly (its clamp range inverts when `numPriorities == 0`). Converted all of these to `throw std::invalid_argument`/ `folly::throw_exception<std::invalid_argument>`, matching this directory's existing convention (`FunctionScheduler.cpp`, `Codel.cpp`) of throwing rather than `CHECK`ing for constructor-argument validation. Reviewed By: derolf Differential Revision: D119818490 fbshipit-source-id: f2f394a5845bd6c785833d484d7de4dcee6096a4

atomic_fetch_min, atomic_fetch_max Summary: Add `atomic_fetch_min` and `atomic_fetch_max` to mimic `std::atomic::fetch_min` and `std::atomic_fetch_max`, with fallbacks in terms of `atomic_fetch_modify`. Reviewed By: ot Differential Revision: D117391575 fbshipit-source-id: c2a40d5f89318e0a5ec690bf9aeb15fc537023a2

atomic_fetch_cond_{op} Summary: Add `atomic_fetch_min_cond`, `atomic_fetch_max_cond`, `atomic_fetch_set_cond`, and `atomic_fetch_reset_cond`, running parallel to the existing `atomic_fetch_{op}` operations. The distinction is that the existing operations are read-modify-writes: they store unconditionally, and so always produce a release edge and always take the cache line exclusively. The `_cond` forms do a trial load first and store only if the value is not already converged. That makes them the right form for high-water marks, min/max stats counters, and idempotent flag bits, where the common steady-state case is that nothing needs to change. This is a real semantic difference, not just an optimization, so the two families are spelled differently rather than one silently becoming the other. A caller which depends on the release edge, or on the operation appearing in the modification order, wants the unconditional form. The doc comments state which each one is. Both families keep the same memory-order parameters as before. It is up to the caller to understand the semantics and choose accordingly. Note there is deliberately no `atomic_fetch_flip_cond`: a flip always changes the bit, so there is nothing to elide. On the fallback path the guard is re-tested on every compare-exchange retry, not only before the loop. A racing writer which converges the value mid-loop therefore ends the loop rather than storing a value that is no longer an improvement. This matters for adoption: the hand-rolled loops these operations are meant to replace overwhelmingly re-test on retry, so without it the library form would be a behaviour change at those call sites rather than a drop-in. Uncontended microbenchmarks: ~19x faster when converged, ~10% slower when advancing, the latter being the cost of the extra trial load. Reviewed By: dmm-fb Differential Revision: D118286954 fbshipit-source-id: 2a43fd69e25d7aab4bd3062fe17b84b93e050244

fixes and tweaks to to_ascii Summary: * Fix `to_ascii_size_clzll`. It returned incorrect digit counts for most bases. `to_ascii_size_route` only sends power-of-two bases and base 10 to it, and for exactly those the old approximation was already exact, meaning that this bug was not seen in practice. But nevertheless. * Fix `char[N]` overloads. They `char[N]` overload of `to_ascii_with_route` bypassed the `kIsMobile` dispatch. * Fix various documentation errors. Reviewed By: dmm-fb Differential Revision: D117892814 fbshipit-source-id: b81ec5c0639f4c4906101f09645a05632a011830

support relaxed_atomic in atomic_fetch_* operations Summary: The `atomic_fetch_*` operations in `folly/synchronization/AtomicUtil.h` did not compile against `folly::relaxed_atomic`. `relaxed_atomic` deliberately omits the `std::memory_order` parameter from every member function, while the operations unconditionally passed one to `load` and to `compare_exchange_weak`. That is an awkward gap, since `relaxed_atomic` is exactly the type reached for on the stats counters and high-water marks which are the natural audience for `atomic_fetch_max` and `atomic_fetch_min`. Add trait `atomic_accepts_memory_order_v`, which gives whether the operations of a type which is atomic-like accept a memory order. It is detected via member `load`, under the convention that such a type accepts a memory order either on all of its operations or on none of them. Split each operation's single `operator()` with a defaulted memory-order parameter into two overloads: one taking no memory order, and one taking a memory order and constrained with `requires(atomic_accepts_memory_order_v<Atomic>)`. So passing a memory order to a `relaxed_atomic` is now ill-formed rather than silently ignored - for such a type there is no memory order to apply. This applies uniformly to `atomic_fetch_set`, `atomic_fetch_reset`, `atomic_fetch_flip`, `atomic_fetch_modify`, `atomic_fetch_min`, and `atomic_fetch_max`. For the bit operations, the `*_fallback` function objects gain overloads taking no memory order, and types which are order-free route to the fallback rather than to `*_native`. This costs nothing: every native path is selected by overload resolution on `std::atomic` or on atomic-ref, and `relaxed_atomic` derives from `std::atomic` protectedly, so it could never have bound to them. `atomic_fetch_min` and `atomic_fetch_max` additionally detect the 1-argument `fetch_min(T)` / `fetch_max(T)` member form. `relaxed_atomic` already declares these under the C++26 `__cpp_lib_atomic_min_max` gate, so without this it would have been stuck on the c/x-loop fallback even once that gate opens. `RelaxedAtomic.h` needs no change - `value_type`, `load`, and `compare_exchange_weak` are already accessible on all four of its shapes. Source-compatible with every existing call site: all of them pass a memory order and use `std::atomic` or `atomic_ref`, and the two overloads differ in arity, so no call becomes ambiguous. The two duck-typed fixtures in the test gain a `load`, which they had lacked only because no code path had previously needed one. Reviewed By: dmm-fb Differential Revision: D118182802 fbshipit-source-id: 99aa8f9908a831ede10761c17cf68d9189917f68

add data() to vector-hash-table containers Summary: Give `F14VectorSet`, `F14VectorMap`, `heap_vector_set`, `heap_vector_map`, `sorted_vector_set`, and `sorted_vector_map` a `data()` member, like `std::vector::data()`, alongside their existing `size()` and `as_span()`. `heap_vector_map` and `sorted_vector_map` already had a const-only `data()` inherited/defined for internal use; this adds the missing mutable overload so it matches the mutable overload their `as_span()` already exposes. `F14VectorSet` and `F14VectorMap` had no `data()` at all; this adds it, following the same constness pattern as `as_span()` (always-const for sets, mutable/const pair for maps). `as_span()` is now implemented in terms of `data()` and `size()` in all six classes, instead of duplicating the pointer/size computation. landed-with-radar-review Reviewed By: DenisYaroshevskiy Differential Revision: D120426363 fbshipit-source-id: 7a578fa024ccf2275193526fe50f595011e4f7c8

folly: set errno in Windows flock shim so try_lock() returns false Summary: On Windows, `folly::File::try_lock()` / `try_lock_shared()` threw a `std::system_error` on lock contention instead of returning `false` like POSIX. Root cause: the Windows `flock` shim in `xplat/folly/portability/SysFile.cpp` returned `-1` on `LockFileEx`/`UnlockFile` failure without setting `errno`. `File::doTryLock` only returns `false` when `errno == EWOULDBLOCK`, so on Windows it fell through to `checkUnixError`, which threw. Fix (Windows-only, inside the existing `#ifdef _WIN32` block; mirrors the errno-mapping precedent in `Unistd.cpp`): - `LockFileEx` failure with `ERROR_LOCK_VIOLATION`/`ERROR_IO_PENDING` → `errno = EWOULDBLOCK` (contention). - Other `LockFileEx`/`UnlockFile` failures → `errno = EIO`. - Invalid handle → `errno = EBADF`. POSIX paths and the blocking `lock()` path are unchanged, so existing callers cannot regress. Adds a portable regression test (`SysFileTest.cpp`) exercising two independent descriptors to one file — flock locks contend per-open-description on POSIX and per-HANDLE on Windows — plus a `ci.windows` label so it runs on Windows CI. [Session trajectory link](https://www.internalfb.com/intern/devai/devmate/inspector/?id=aced5223-8ee9-4036-84a3-181a34047517) Reviewed By: dmm-fb Differential Revision: D117576786 fbshipit-source-id: 5e78c64baaf7c3bd5e464dee217b7417abc452e6

folly/io/async: return -1/EOPNOTSUPP instead of crashing on unsupported UDP write options Summary: Several `AsyncUDPSocket` write paths used `CHECK`/`CHECK_LT` to reject combinations of caller-supplied options that aren't supported, rather than returning the graceful `-1`/`errno` failure these same functions already use for other unsupported-option cases right next to these checks (e.g. `connectedAddress_ != address` at `writeChain`, `!additionalCmsgs.empty()` at `writeWithCmsgsImpl`). None of these are internal invariant violations — they're ordinary caller/config mismatches: - `writeChain`: `nontrivialCmsgs_.empty()` — the single-`IOBuf` `writeChain` path doesn't serialize `setNontrivialCmsgs()`/`appendNontrivialCmsgs()` entries; only `writeWithCmsgs()` and friends do. - `writeChain`, `writeWithCmsgsImpl`, `writemGSO`, `writemGSOv`: `gso`/ `txTime` options requested on a platform without `MSG_ERRQUEUE` (the `#ifndef FOLLY_HAVE_MSG_ERRQUEUE` branches) — `writemGSO`/`writemGSOv`'s own doc comments already tell callers to check `getGSO()` before passing a positive value, so this converts an unenforced doc precondition into an enforced, recoverable one instead of a crash. Reviewed By: derolf Differential Revision: D119818484 fbshipit-source-id: a2a1466f4f6a90bd1dc4eec6dde7b0d1cb541a07

fix atomic_grow_array iterator operators Summary: The iterators claim `std::random_access_iterator_tag` but do not model `std::random_access_iterator`: * `<`, `<=`, `>`, `>=` reference `lhs.index` instead of `lhs.index_`, so they fail to compile when used. * `operator*`, `operator+`, `operator-(n)`, and `operator[]` are non-const, so they cannot be used on a const iterator. * `operator--`, `operator->`, and `n + it` are missing. Fix these, and add tests including `std::random_access_iterator` and `std::ranges::random_access_range` static assertions and `std::ranges::sort` over a view. ___ Differential Revision: D122098867 fbshipit-source-id: ef1a16a1410976454883e3e04ae02a2291766214