Followup to #30769
I grepped for `try .*toOwnedSlice` and checked all of them by hand.
Fixes a bunch of memory leaks removes usages or `errdefer` and `vars` in some places. I also switched array_list.Managed to ArrayList where it was convenient.
Reviewed-on: https://codeberg.org/ziglang/zig/pulls/32001
Reviewed-by: Andrew Kelley <andrew@ziglang.org>
- New Features
-- Multiprocess Fuzzing
The fuzzer now is able to utilize multiple cores. This is controllable
with the `-j` build option. Limited fuzzing still uses one core.
-- Fuzzing Infinite Mode
When provided multiple tests, the fuzzer now switches between them and
prioritizes the most effective and interesting ones. Over time already
explored tests will become barely run compared to tests yielding new
inputs.
-- Crash Dumps
Crashing inputs are now saved to a file indicated by the crash message.
It is recommended to use these files to reproduce the crash using
`std.testing.FuzzInputOptions.corpus` and @embedFile.
- Design
Each fuzzing process is assigned an instance id which has the following
uses:
* In conjunction with the pc hash and running test index, they uniquely
identify input files in the case of a crash.
* It is combined with the test seed for a unique rng seed.
* Instance 0 is solely responsible for syncing the filesystem corpus.
When new inputs are found, they are sent to the build server. It then
distributes the new input to the other instances. Each instance has a
concurrent poller managed by the test runner which sends received
inputs to libfuzzer. (note that this is affected by #31718 and so can
(rarely) deadlock)
For fuzzing infinite mode, the test runner now receives a list of tests
from the build server. The fuzzer runs tests in batches of one second,
approximated in cycles by the previous batch's run speed. Tests finding
new inputs or with few runs are given a higher run chance. The baseline
run chance is based off the recency of the last find and the number of
pcs the test has hit.
Users can proceed by telling the build system how much memory to assume
the system has. I have improved the failure message to communicate this.
Partially reverts 87f8f47ba5
Even if we wanted to unrevert this reverted commit, it's not sufficient
to merely downgrade the failure to a warning, because the main
scheduling logic will fail to schedule steps that have a max_rss
exceeding the detected system value, causing some steps to never get
executed, eventually tripping an assert. Such a change would need to
also override the max_rss value to be equal to the greatest value across
all steps.
closes#31510
The indexes can change between recompilation due to conditional
compilation and compiler quirks. While unit test names are still not a
perfect solution, they are better than indexes.
Now that zig1.wasm is updated, apply the matching standard library
changes.
The main one is in `std.builtin.Type`, where `alignment` fields now have
type `?usize` rather than `comptime_int`.
Additionally, we need to add explicit backing integers to some packed
unions, because (due to https://github.com/ziglang/zig/issues/24714)
they need explicit backing integers to be used in `extern` contexts.
This change could not happen before now, because prior to this branch,
packed unions did not allow explicit backing integer types (that is,
this branch implemented https://github.com/ziglang/zig/issues/25350).
On Windows, it is sometimes problematic to depend on ws2_32.dll. Before,
users of std.Io.Threaded would have to call ioBasic() rather than io()
in order to avoid unnecessary dependencies on ws2_32.dll. Now, the
application can disable networking with std.Options.
This change is necessary due to moving networking functionality to
be based on Io.Operation, which is a tagged union.
The tar format expects `/`, although some untar implementations do seem to handle Windows-style `\` path separators (7-Zip at least).
The tar.Writer API can't really enforce this, though, as doing so would effectively make `\` an illegal character when it's really not. So, it's up to the user to provide paths with the correct path separators.
`Build/WebServer.zig` will still output tars with `\` as a path separator on Windows, but that's currently only used during fuzzing which is not yet implemented on Windows.
Modifies the `Allocator` implementation provided by `ArenaAllocator` to be
threadsafe using only atomics and no synchronization primitives locked
behind an `Io` implementation.
At its core this is a lock-free singly linked list which uses CAS loops to
exchange the head node. A nice property of `ArenaAllocator` is that the
only functions that can ever remove nodes from its linked list are `reset`
and `deinit`, both of which are not part of the `Allocator` interface and
thus aren't threadsafe, so node-related ABA problems are impossible.
There *are* some trade-offs: end index tracking is now per node instead of
per allocator instance. It's not possible to publish a head node and its
end index at the same time if the latter isn't part of the former.
Another compromise had to be made in regards to resizing existing nodes.
Annoyingly, `rawResize` of an arbitrary thread-safe child allocator can
of course never be guaranteed to be an atomic operation, so only one
`alloc` call can ever resize at the same time, other threads have to
consider any resizes they attempt during that time failed. This causes
slightly less optimal behavior than what could be achieved with a mutex.
The LSB of `Node.size` is used to signal that a node is being resized.
This means that all nodes have to have an even size.
Calls to `alloc` have to allocate new nodes optimistically as they can
only know whether any CAS on a head node will succeed after attempting it,
and to attempt the CAS they of course already need to know the address of
the freshly allocated node they are trying to make the new head.
The simplest solution to this would be to just free the new node again if
a CAS fails, however this can be expensive and would mean that in practice
arenas could only really be used with a GPA as their child allocator. To
work around this, this implementation keeps its own free list of nodes
which didn't make their CAS to be reused by a later `alloc` invocation.
To keep things simple and avoid ABA problems the free list is only ever
be accessed beyond its head by 'stealing' the head node (and thus the
entire list) with an atomic swap. This makes iteration and removal trivial
since there's only ever one thread doing it at a time which also owns all
nodes it's holding. When the thread is done it can just push its list onto
the free list again.
This implementation offers comparable performance to the previous one when
only being accessed by a single thread and a slight speedup compared to
the previous implementation wrapped into a `ThreadSafeAllocator` up to ~7
threads performing operations on it concurrently.
(measured on a base model MacBook Pro M1)
-- On the standard library side:
The `input: []const u8` parameter of functions passed to `testing.fuzz`
has changed to `smith: *testing.Smith`. `Smith` is used to generate
values from libfuzzer or input bytes generated by libfuzzer.
`Smith` contains the following base methods:
* `value` as a generic method for generating any type
* `eos` for generating end-of-stream markers. Provides the additional
guarantee `true` will eventually by provided.
* `bytes` for filling a byte array.
* `slice` for filling part of a buffer and providing the length.
`Smith.Weight` is used for giving value ranges a higher probability of
being selected. By default, every value has a weight of zero (i.e. they
will not be selected). Weights can only apply to values that fit within
a u64. The above functions have corresponding ones that accept weights.
Additionally, the following functions are provided:
* `baselineWeights` which provides a set of weights containing every
possible value of a type.
* `eosSimpleWeighted` for unique weights for `true` and `false`
* `valueRangeAtMost` and `valueRangeLessThan` for weighing only a range
of values.
-- On the libfuzzer and abi side:
--- Uids
These are u32s which are used to classify requested values. This solves
the problem of a mutation causing a new value to be requested and
shifting all future values; for example:
1. An initial input contains the values 1, 2, 3 which are interpreted
as a, b, and c respectively by the test.
2. The 1 is mutated to a 4 which causes the test to request an extra
value interpreted as d. The input is now 4, 2, 3, 5 (new value) which
the test corresponds to a, d, b, c; however, b and c no longer
correspond to their original values.
Uids contain a hash component and type component. The hash component
is currently determined in `Smith` by taking a hash of the calling
`@returnAddress()` or via an argument in the corresponding `WithHash`
functions. The type component is used extensively in libfuzzer with its
hashmaps.
--- Mutations
At the start of a cycle (a run), a random number of values to mutate is
selected with less being exponentially more likely. The indexes of the
values are selected from a selected uid with a logarithmic bias to uids
with more values.
Mutations may change a single values, several consecutive values in a
uid, or several consecutive values in the uid-independent order they
were requested. They may generate random values, mutate from previous
ones, or copy from other values in the same uid from the same input or
spliced from another.
For integers, mutations from previous ones currently only generates
random values. For bytes, mutations from previous mix new random data
and previous bytes with a set number of mutations.
--- Passive Minimization
A different approach has been taken for minimizing inputs: instead of
trying a fixed set of mutations when a fresh input is found, the input
is instead simply added to the corpus and removed when it is no longer
valuable.
The quality of an input is measured based off how many unique pcs it
hit and how many values it needed from the fuzzer. It is tracked which
inputs hold the best qualities for each pc for hitting the minimum and
maximum unique pcs while needing the least values.
Once all an input's qualities have been superseded for the pcs it hit,
it is removed from the corpus.
-- Comparison to byte-based smith
A byte-based smith would be much more inefficient and complex than this
solution. It would be unable to solve the shifting problem that Uids
do. It is unable to provide values from the fuzzer past end-of-stream.
Even with feedback, it would be unable to act on dynamic weights which
have proven essential with the updated tests (e.g. to constrain values
to a range).
-- Test updates
All the standard library tests have been updated to use the new smith
interface. For `Deque`, an ad hoc allocator was written to improve
performance and remove reliance on heap allocation. `TokenSmith` has
been added to aid in testing Ast and help inform decisions on the smith
interface.
Importantly, adds ability to get Clock resolution, which may be zero.
This allows error.Unexpected and error.ClockUnsupported to be removed
from timeout and clock reading error sets.
- delete std.Thread.Futex
- delete std.Thread.Mutex
- delete std.Thread.Semaphore
- delete std.Thread.Condition
- delete std.Thread.RwLock
- delete std.once
std.Thread.Mutex.Recursive remains... for now. it will be replaced with
a special purpose mechanism used only by panic logic.
std.Io.Threaded exposes mutexLock and mutexUnlock for the advanced case
when you need to call them directly.
In Zig standard library, Dir means an open directory handle. path
represents a file system identifier string. This function is better
named after "current path" than "current dir". "get" and "working" are
superfluous.
The previous logic was made really messy by the fact that upon entry to
the step eval worker, the step may not be ready to run, we may be racing
with other workers doing the same check, and we had already acquired our
RSS requirement even though we might not run. It also required iterating
all dependencies each time we were called to check whether we were even
ready to run yet.
A much better strategy is for each step to have an atomic counter
representing how many of its dependencies are yet to complete. When a
step completes (successfully or otherwise), it decrements this value for
all of its dependants, and if it drops any to 0, it schedules that step
to run. This means each step is scheduled exactly once, and only when
all of its dependencies have finished, reducing redundant checks and
hence contention. If the step being scheduled needs to claim RSS which
isn't available, then it is instead added to `memory_blocked_steps`,
which is iterated by the step worker after a step with an RSS claim
finishes.
This logic is more concise than before, simpler to understand, generally
more efficient, and fixes a bug in the RSS tracking. Also, as a nice
side effect, it should also play a little bit nicer with `Io.Threaded`'s
scheduling strategy, because we no longer spawn extremely short-lived
tasks all the time as we previously did.
Resolves: https://codeberg.org/ziglang/zig/issues/30742
Alex Rønne Petersen