| // Copyright 2023 The Centipede Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // This library defines the concepts "fuzzing feature" and "feature domain". |
| // It is used by Centipede, and it can be used by fuzz runners to |
| // define their features in a way most friendly to Centipede. |
| // Fuzz runners do not have to use this file nor to obey the rules defined here. |
| // But using this file and following its rules is the simplest way if you want |
| // Centipede to understand the details about the features generated by the |
| // runner. |
| |
| #ifndef THIRD_PARTY_CENTIPEDE_CONCURRENT_BYTESET_H_ |
| #define THIRD_PARTY_CENTIPEDE_CONCURRENT_BYTESET_H_ |
| |
| #include <climits> |
| #include <cstddef> |
| #include <cstdint> |
| #include <functional> |
| |
| // WARNING!!!: Be very careful with what STL headers or other dependencies you |
| // add here. This header needs to remain mostly bare-bones so that we can |
| // include it into runner. |
| |
| #include "absl/base/const_init.h" |
| |
| namespace centipede { |
| |
| // TODO(kcc): replace the standalone ForEachNonZeroByte with code from here. |
| // TODO(kcc): ConcurrentByteSet is an unoptimized single-layer byte set. |
| // Implement multi-layer byte set(s). |
| |
| // A fixed-size byte set containing kSize bytes, kSize must be a multiple of 64. |
| // Set() can be called concurrently with another Set(), other uses should be |
| // synchronized externally. |
| // Intended usage is to call ForEachNonZeroByte() from one thread. |
| // Should only be constructed with static storage duration. |
| template <size_t kSize> |
| class ConcurrentByteSet { |
| public: |
| static constexpr size_t kSizeInBytes = kSize; |
| // kSize must be multiple of this. |
| static constexpr size_t kSizeMultiple = 64; |
| static_assert((kSize % kSizeMultiple) == 0); |
| |
| // Creates a ConcurrentByteSet with static storage duration. |
| explicit constexpr ConcurrentByteSet(absl::ConstInitType) {} |
| |
| // Clears the set. |
| void clear() { memset(bytes_, 0, sizeof(bytes_)); } |
| |
| // Sets element `idx` to `value`. `idx` must be <= kSize. |
| // Can be called concurrently. |
| void Set(size_t idx, uint8_t value) { |
| if (idx >= kSize) __builtin_trap(); |
| __atomic_store_n(&bytes_[idx], value, __ATOMIC_RELAXED); |
| } |
| |
| // Performs a saturated increment of element `idx`. |
| void SaturatedIncrement(size_t idx) { |
| if (idx >= kSize) __builtin_trap(); |
| uint8_t counter = __atomic_load_n(&bytes_[idx], __ATOMIC_RELAXED); |
| if (counter != 255) |
| __atomic_store_n(&bytes_[idx], counter + 1, __ATOMIC_RELAXED); |
| } |
| |
| // Calls `action(index, value)` for every {index,value} of a non-zero byte in |
| // the set, then sets all those bytes to zero. |
| // `from` and `to` set the range of elements to iterate, both must be |
| // multiples of kSizeMultiple. |
| void ForEachNonZeroByte(const std::function<void(size_t, uint8_t)> &action, |
| size_t from = 0, size_t to = kSize) { |
| using word_t = uintptr_t; |
| constexpr size_t kWordSize = sizeof(word_t); |
| if (from % kSizeMultiple) __builtin_trap(); |
| if (to % kSizeMultiple) __builtin_trap(); |
| if (to > kSize) __builtin_trap(); |
| // Iterate one word at a time. |
| for (uint8_t *ptr = &bytes_[from], *end = &bytes_[to]; ptr < end; |
| ptr += kWordSize) { |
| word_t word; |
| __builtin_memcpy(&word, ptr, kWordSize); |
| if (!word) continue; |
| __builtin_memset(ptr, 0, kWordSize); |
| // This loop assumes little-endianness. (Tests will break on big-endian). |
| for (size_t pos = 0; pos < kWordSize; pos++) { |
| uint8_t value = word >> (pos * CHAR_BIT); // lowest byte is taken. |
| if (value) action(ptr - &bytes_[0] + pos, value); |
| } |
| } |
| } |
| |
| private: |
| uint8_t bytes_[kSize] __attribute__((aligned(64))); // No initializer. |
| }; |
| |
| // Similar to ConcurrentByteSet, but consists of two layers, upper and lower. |
| // The size of the lower layer is a multiple of the size of the upper layer. |
| // Set() writes 1 to an element in the upper layer and then writes `value` to an |
| // element of the lower value. This allows ForEachNonZeroByte() to |
| // skip sub-regions of lower layer that were not written to. Otherwise, the |
| // interface and the behaviour is equivalent to ConcurrentByteSet. |
| template <size_t kSize, typename Upper, |
| typename Lower = ConcurrentByteSet<kSize>> |
| class LayeredConcurrentByteSet { |
| public: |
| static constexpr size_t kSizeInBytes = kSize; |
| static constexpr size_t kSizeMultiple = |
| Lower::kSizeMultiple * Upper::kSizeMultiple; |
| static_assert(kSize == Lower::kSizeInBytes); |
| |
| LayeredConcurrentByteSet() = default; |
| // Creates a LayeredConcurrentByteSet with static storage duration. |
| explicit constexpr LayeredConcurrentByteSet(absl::ConstInitType) |
| : upper_layer_(absl::kConstInit), lower_layer_(absl::kConstInit) {} |
| |
| void clear() { |
| upper_layer_.clear(); |
| lower_layer_.clear(); |
| } |
| |
| void Set(size_t idx, uint8_t value) { |
| if (idx >= kSize) __builtin_trap(); |
| upper_layer_.Set(idx / kLayerRatio, 1); |
| lower_layer_.Set(idx, value); |
| } |
| |
| void SaturatedIncrement(size_t idx) { |
| if (idx >= kSize) __builtin_trap(); |
| upper_layer_.Set(idx / kLayerRatio, 1); |
| lower_layer_.SaturatedIncrement(idx); |
| } |
| |
| void ForEachNonZeroByte(const std::function<void(size_t, uint8_t)> &action, |
| size_t from = 0, size_t to = kSize) { |
| if (to > kSize) __builtin_trap(); |
| if (from % kSizeMultiple) __builtin_trap(); |
| if (to % kSizeMultiple) __builtin_trap(); |
| size_t upper_from = from / kLayerRatio; |
| size_t upper_to = to / kLayerRatio; |
| upper_layer_.ForEachNonZeroByte( |
| [&](size_t idx, uint8_t value) { |
| size_t lower_from = idx * kLayerRatio; |
| size_t lower_to = lower_from + kLayerRatio; |
| lower_layer_.ForEachNonZeroByte(action, lower_from, lower_to); |
| }, |
| upper_from, upper_to); |
| } |
| |
| private: |
| Upper upper_layer_; |
| Lower lower_layer_; |
| static constexpr size_t kLayerRatio = |
| Lower::kSizeInBytes / Upper::kSizeInBytes; |
| static_assert((Lower::kSizeInBytes % Upper::kSizeInBytes) == 0); |
| }; |
| |
| // Two-layer ConcurrentByteSet() with upper layer 64x smaller than the lower. |
| template <size_t kSize> |
| class TwoLayerConcurrentByteSet |
| : public LayeredConcurrentByteSet<kSize, ConcurrentByteSet<kSize / 64>> { |
| public: |
| // Creates a TwoLayerConcurrentByteSet with static storage duration. |
| explicit constexpr TwoLayerConcurrentByteSet(absl::ConstInitType) |
| : LayeredConcurrentByteSet<kSize, ConcurrentByteSet<kSize / 64>>( |
| absl::kConstInit) {} |
| }; |
| |
| } // namespace centipede |
| |
| #endif // THIRD_PARTY_CENTIPEDE_CONCURRENT_BYTESET_H_ |