| // Copyright 2021 The Fuchsia Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #include "src/sys/fuzzing/realmfuzzer/engine/module-proxy.h" | |
| #include <lib/syslog/cpp/macros.h> | |
| namespace fuzzing { | |
| namespace { | |
| // Convert counter values to "features" in the same manner as AFL, described here: | |
| // http://lcamtuf.coredump.cx/afl/technical_details.txt. | |
| // | |
| // This implementation is based on the one used by libFuzzer. Do not try to optimize this further; | |
| // as written the compiler is able to effectively optimize it at -O2 and higher. | |
| uint8_t to_feature(uint8_t counter) { | |
| uint8_t feature = 0; | |
| if (counter >= 128) { | |
| feature = 1 << 7; | |
| } else if (counter >= 32) { | |
| feature = 1 << 6; | |
| } else if (counter >= 16) { | |
| feature = 1 << 5; | |
| } else if (counter >= 8) { | |
| feature = 1 << 4; | |
| } else if (counter >= 4) { | |
| feature = 1 << 3; | |
| } else if (counter >= 3) { | |
| feature = 1 << 2; | |
| } else if (counter >= 2) { | |
| feature = 1 << 1; | |
| } else if (counter >= 1) { | |
| feature = 1 << 0; | |
| } | |
| return feature; | |
| } | |
| // Sums two groups of 8 counters. | |
| // | |
| // Sums exceeding 0x7f map to the same feature and don't need to be distinguished. This means we | |
| // can get the right features by simply adding 7-bits of each byte in parallel and ORing the | |
| // high bits. This avoids overflowing from one byte to the next. | |
| uint64_t sum_counters(uint64_t a, uint64_t b) { | |
| constexpr uint64_t kHiBitsMask = 0x80'80'80'80'80'80'80'80ULL; | |
| uint64_t hi_bits = (a | b) & kHiBitsMask; | |
| return ((a & ~kHiBitsMask) + (b & ~kHiBitsMask)) | hi_bits; | |
| } | |
| } // namespace | |
| ModuleProxy::ModuleProxy(const std::string& id, size_t size) | |
| : id_(id), | |
| features_len_((size + sizeof(uint64_t) - 1) / sizeof(uint64_t)), | |
| extra_bytes_(size % sizeof(uint64_t)) { | |
| FX_CHECK(size != 0); | |
| features_.reset(new uint64_t[features_len_]); | |
| accumulated_.reset(new uint64_t[features_len_]); | |
| Clear(); | |
| } | |
| void ModuleProxy::Add(void* counters, size_t size) { | |
| FX_CHECK(features_len_ == ((size + sizeof(uint64_t) - 1) / sizeof(uint64_t))); | |
| FX_CHECK(extra_bytes_ == (size % sizeof(uint64_t))); | |
| // This method expects 64-bit alignment to simplify iteration. | |
| FX_CHECK(reinterpret_cast<uintptr_t>(counters) % sizeof(uint64_t) == 0); | |
| counters_.push_back(reinterpret_cast<uint64_t*>(counters)); | |
| } | |
| void ModuleProxy::Remove(void* counters) { | |
| counters_.erase( | |
| std::remove(counters_.begin(), counters_.end(), reinterpret_cast<uint64_t*>(counters)), | |
| counters_.end()); | |
| } | |
| size_t ModuleProxy::Measure() { return MeasureImpl(/* accumulate */ false); } | |
| size_t ModuleProxy::Accumulate() { return MeasureImpl(/* accumulate */ true); } | |
| size_t ModuleProxy::MeasureImpl(bool accumulate) { | |
| size_t num_new_features = 0; | |
| memset(features_.get(), 0, features_len_ * sizeof(uint64_t)); | |
| size_t counters_len = extra_bytes_ == 0 ? features_len_ : features_len_ - 1; | |
| // First, sum all counters into the features array. | |
| for (auto* counters : counters_) { | |
| for (size_t i = 0; i < counters_len; ++i) { | |
| if (counters[i]) { | |
| features_[i] = sum_counters(counters[i], features_[i]); | |
| } | |
| } | |
| if (extra_bytes_ != 0) { | |
| // Handle the last, incomplete 64 bit block. | |
| uint64_t counter = 0; | |
| memcpy(&counter, &counters[counters_len], extra_bytes_); | |
| features_[counters_len] = sum_counters(counter, features_[counters_len]); | |
| } | |
| } | |
| // Next, convert the summed counters to features. | |
| for (size_t i = 0; i < features_len_; ++i) { | |
| if (features_[i]) { | |
| uint8_t* feature = reinterpret_cast<uint8_t*>(&features_[i]); | |
| for (size_t j = 0; j < sizeof(uint64_t); ++j) { | |
| feature[j] = static_cast<uint8_t>(to_feature(feature[j])); | |
| } | |
| num_new_features += __builtin_popcountll(~accumulated_[i] & features_[i]); | |
| if (accumulate) { | |
| accumulated_[i] |= features_[i]; | |
| } | |
| } | |
| } | |
| return num_new_features; | |
| } | |
| size_t ModuleProxy::GetCoverage(size_t* out_num_features) { | |
| size_t num_pcs = 0; | |
| size_t num_features = 0; | |
| for (size_t i = 0; i < features_len_; ++i) { | |
| auto accumulated = accumulated_[i]; | |
| if (accumulated) { | |
| num_features += __builtin_popcountll(accumulated_[i]); | |
| for (; accumulated; accumulated >>= 8) { | |
| if (accumulated & 0xff) { | |
| num_pcs++; | |
| } | |
| } | |
| } | |
| } | |
| if (out_num_features) { | |
| *out_num_features = num_features; | |
| } | |
| return num_pcs; | |
| } | |
| void ModuleProxy::Clear() { memset(accumulated_.get(), 0, features_len_ * sizeof(uint64_t)); } | |
| } // namespace fuzzing |