1 // Copyright 2024 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <cstddef> 17 18 namespace pw::allocator { 19 20 // inclusive-language: disable 21 22 /// Information that can be used to represent the fragmentation of the block 23 /// allocator's memory region. 24 /// 25 /// Fragmentation can be measured as 1 minus the normalized root-sum-square of 26 /// the free block inner sizes, i.e. 27 /// 28 /// 1 - (sqrt(sum(U[i]^2)) / sum(U[i]) 29 /// 30 /// where `U[i]` is the inner size of the i-th free block. 31 /// 32 /// This metric has been described by Adam Sawicki 33 /// (https://asawicki.info/news_1757_a_metric_for_memory_fragmentation), 34 /// and used in esp8266/Arduino 35 /// (https://github.com/esp8266/Arduino/blob/master/cores/esp8266/Esp-frag.cpp), 36 /// among others. 37 /// 38 /// This struct provides the sum-of-squares and the sum of the inner sizes of 39 /// free blocks. It is left to the caller to perform the square root and 40 /// division steps, perhaps on a host, AP, or other device with better floating 41 /// point support. 42 /// 43 /// The sum-of-squares is stored as a pair of sizes, since it can overflow. 44 struct Fragmentation { 45 /// Sum-of-squares of the inner sizes of free blocks. 46 struct { 47 size_t hi = 0; 48 size_t lo = 0; 49 } sum_of_squares; 50 51 /// Sum of the inner sizes of free blocks. 52 size_t sum = 0; 53 54 void AddFragment(size_t inner_size); 55 }; 56 57 // inclusive-language: enable 58 59 /// Perform the final steps of calculating the fragmentation metric. 60 /// 61 /// This step includes manipulating floating point numbers, and as such it may 62 /// be desirable to avoid performing this step on device. 63 float CalculateFragmentation(const Fragmentation& fragmentation); 64 65 } // namespace pw::allocator 66