Line data Source code
1 : /* 2 : Copyright 2018-2024, Barcelona Supercomputing Center (BSC), Spain 3 : Copyright 2015-2024, Johannes Gutenberg Universitaet Mainz, Germany 4 : 5 : This software was partially supported by the 6 : EC H2020 funded project NEXTGenIO (Project ID: 671951, www.nextgenio.eu). 7 : 8 : This software was partially supported by the 9 : ADA-FS project under the SPPEXA project funded by the DFG. 10 : 11 : This file is part of GekkoFS. 12 : 13 : GekkoFS is free software: you can redistribute it and/or modify 14 : it under the terms of the GNU General Public License as published by 15 : the Free Software Foundation, either version 3 of the License, or 16 : (at your option) any later version. 17 : 18 : GekkoFS is distributed in the hope that it will be useful, 19 : but WITHOUT ANY WARRANTY; without even the implied warranty of 20 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 : GNU General Public License for more details. 22 : 23 : You should have received a copy of the GNU General Public License 24 : along with GekkoFS. If not, see <https://www.gnu.org/licenses/>. 25 : 26 : SPDX-License-Identifier: GPL-3.0-or-later 27 : */ 28 : 29 : #ifndef GKFS_COMMON_ARITHMETIC_HPP 30 : #define GKFS_COMMON_ARITHMETIC_HPP 31 : 32 : #include <cstdint> 33 : #include <unistd.h> 34 : #include <cassert> 35 : 36 : namespace gkfs::utils::arithmetic { 37 : 38 : /** 39 : * Check whether integer `n` is a power of 2. 40 : * 41 : * @param [in] n the number to check. 42 : * @returns `true` if `n` is a power of 2; `false` otherwise. 43 : */ 44 : constexpr bool 45 51741437 : is_power_of_2(uint64_t n) { 46 51741279 : return n && (!(n & (n - 1u))); 47 : } 48 : 49 : /** 50 : * Compute the base2 logarithm for 64 bit integers. 51 : * 52 : * @param [in] n the number from which to compute the log2. 53 : * @returns the base 2 logarithm of `n`. 54 : */ 55 : constexpr std::size_t 56 5564647 : log2(uint64_t n) { 57 5564647 : return 8u * sizeof(uint64_t) - __builtin_clzll(n) - 1; 58 : } 59 : 60 : /** 61 : * Check whether @n is aligned to a block boundary, i.e. if it is divisible by 62 : * @block_size. 63 : * 64 : * @note This function assumes that block_size is a power of 2. 65 : * 66 : * @param [in] n the number to check. 67 : * @param [in] block_size 68 : * @returns true if @n is divisible by @block_size; false otherwise. 69 : */ 70 : constexpr bool 71 2806845 : is_aligned(const uint64_t n, const size_t block_size) { 72 2806845 : using gkfs::utils::arithmetic::log2; 73 2806845 : assert(is_power_of_2(block_size)); 74 2806845 : return !(n & ((1u << log2(block_size)) - 1)); 75 : } 76 : 77 : /** 78 : * Given a file @offset and a @block_size, align the @offset to its 79 : * closest left-side block boundary. 80 : * 81 : * @note This function assumes that block_size is a power of 2. 82 : * 83 : * @param [in] offset the offset to align. 84 : * @param [in] block_size the block size used to compute boundaries. 85 : * @returns an offset aligned to the left-side block boundary. 86 : */ 87 : constexpr uint64_t 88 5529114 : align_left(const uint64_t offset, const size_t block_size) { 89 : // This check is automatically removed in release builds 90 5529114 : assert(is_power_of_2(block_size)); 91 5529114 : return offset & ~(block_size - 1u); 92 : } 93 : 94 : 95 : /** 96 : * Given a file @offset and a @block_size, align the @offset to its 97 : * closest right-side block boundary. 98 : * 99 : * @note This function assumes that block_size is a power of 2. 100 : * 101 : * @param [in] offset the offset to align. 102 : * @param [in] block_size the block size used to compute boundaries. 103 : * @returns an offset aligned to the right-side block boundary. 104 : */ 105 : constexpr uint64_t 106 13742 : align_right(const uint64_t offset, const size_t block_size) { 107 : // This check is automatically removed in release builds 108 13742 : assert(is_power_of_2(block_size)); 109 13742 : return align_left(offset, block_size) + block_size; 110 : } 111 : 112 : 113 : /** 114 : * Return the overrun bytes that separate @offset from the closest left side 115 : * block boundary. 116 : * 117 : * @note This function assumes that block_size is a power of 2. 118 : * 119 : * @param [in] offset the offset for which the overrun distance should be 120 : * computed. 121 : * @param [in] block_size the block size used to compute boundaries. 122 : * @returns the distance in bytes between the left-side boundary of @offset 123 : */ 124 : constexpr size_t 125 7009 : block_overrun(const uint64_t offset, const size_t block_size) { 126 : // This check is automatically removed in release builds 127 7009 : assert(is_power_of_2(block_size)); 128 7009 : return offset & (block_size - 1u); 129 : } 130 : 131 : 132 : /** 133 : * Return the underrun bytes that separate @offset from the closest right side 134 : * block boundary. 135 : * 136 : * @note This function assumes that block_size is a power of 2. 137 : * 138 : * @param [in] offset the offset for which the overrun distance should be 139 : * computed. 140 : * @param [in] block_size the block size used to compute boundaries. 141 : * @returns the distance in bytes between the right-side boundary of @offset 142 : */ 143 : constexpr size_t 144 6925 : block_underrun(const uint64_t offset, const size_t block_size) { 145 : // This check is automatically removed in release builds 146 6925 : assert(is_power_of_2(block_size)); 147 6925 : return align_right(offset, block_size) - offset; 148 : } 149 : 150 : 151 : /** 152 : * Given an @offset and a @block_size, compute the block index to which @offset 153 : * belongs. 154 : * 155 : * @note Block indexes are (conceptually) computed by dividing @offset 156 : * by @block_size, with index 0 referring to block [0, block_size - 1], 157 : * index 1 to block [block_size, 2 * block_size - 1], and so on up to 158 : * a maximum index FILE_LENGTH / block_size. 159 : * 160 : * @note This function assumes that @block_size is a power of 2. 161 : * 162 : * @param [in] offset the offset for which the block index should be computed. 163 : * @param [in] block_size the block_size that should be used to compute the 164 : * index. 165 : * @returns the index of the block containing @offset. 166 : */ 167 : constexpr uint64_t 168 7049 : block_index(const uint64_t offset, const size_t block_size) { 169 : 170 7049 : using gkfs::utils::arithmetic::log2; 171 : 172 : // This check is automatically removed in release builds 173 7049 : assert(is_power_of_2(block_size)); 174 7049 : return align_left(offset, block_size) >> log2(block_size); 175 : } 176 : 177 : 178 : /** 179 : * Compute the number of blocks involved in an operation affecting the 180 : * regions from [@offset, to @offset + @count). 181 : * 182 : * @note This function assumes that @block_size is a power of 2. 183 : * @note This function assumes that @offset + @count does not 184 : * overflow. 185 : * 186 : * @param [in] offset the operation's initial offset. 187 : * @param [in] size the number of bytes affected by the operation. 188 : * @param [in] block_size the block size that should be used to compute the 189 : * number of blocks. 190 : * @returns the number of blocks affected by the operation. 191 : */ 192 : constexpr std::size_t 193 2750753 : block_count(const uint64_t offset, const size_t size, const size_t block_size) { 194 : 195 2750753 : using gkfs::utils::arithmetic::log2; 196 : 197 : // These checks are automatically removed in release builds 198 2750753 : assert(is_power_of_2(block_size)); 199 : 200 : #if defined(__GNUC__) && !defined(__clang__) 201 2750753 : assert(!__builtin_add_overflow_p(offset, size, uint64_t{0})); 202 : #else 203 : assert(offset + size > offset); 204 : #endif 205 : 206 2750753 : const uint64_t first_block = align_left(offset, block_size); 207 2750753 : const uint64_t final_block = align_left(offset + size, block_size); 208 2750753 : const size_t mask = -!!size; // this is either 0 or ~0 209 : 210 2750753 : return (((final_block >> log2(block_size)) - 211 5501506 : (first_block >> log2(block_size)) + 212 2750753 : !is_aligned(offset + size, block_size))) & 213 2750753 : mask; 214 : } 215 : 216 : } // namespace gkfs::utils::arithmetic 217 : 218 : #endif // GKFS_COMMON_ARITHMETIC_HPP