| 1 | /* |
| 2 | * QEMU 64-bit address ranges |
| 3 | * |
| 4 | * Copyright (c) 2015-2016 Red Hat, Inc. |
| 5 | * |
| 6 | * This program is free software; you can redistribute it and/or |
| 7 | * modify it under the terms of the GNU General Public |
| 8 | * License as published by the Free Software Foundation; either |
| 9 | * version 2 of the License, or (at your option) any later version. |
| 10 | * |
| 11 | * This program is distributed in the hope that it will be useful, |
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 14 | * General Public License for more details. |
| 15 | * |
| 16 | * You should have received a copy of the GNU General Public License |
| 17 | * along with this program; if not, see <http://www.gnu.org/licenses/>. |
| 18 | */ |
| 19 | |
| 20 | #ifndef QEMU_RANGE_H |
| 21 | #define QEMU_RANGE_H |
| 22 | |
| 23 | #include "qemu/bitops.h" |
| 24 | |
| 25 | /* |
| 26 | * Operations on 64 bit address ranges. |
| 27 | * Notes: |
| 28 | * - Ranges must not wrap around 0, but can include UINT64_MAX. |
| 29 | */ |
| 30 | |
| 31 | struct Range { |
| 32 | /* |
| 33 | * Do not access members directly, use the functions! |
| 34 | * A non-empty range has @lob <= @upb. |
| 35 | * An empty range has @lob == @upb + 1. |
| 36 | */ |
| 37 | uint64_t lob; /* inclusive lower bound */ |
| 38 | uint64_t upb; /* inclusive upper bound */ |
| 39 | }; |
| 40 | |
| 41 | static inline void range_invariant(const Range *range) |
| 42 | { |
| 43 | assert(range->lob <= range->upb || range->lob == range->upb + 1); |
| 44 | } |
| 45 | |
| 46 | /* Compound literal encoding the empty range */ |
| 47 | #define range_empty ((Range){ .lob = 1, .upb = 0 }) |
| 48 | |
| 49 | /* Is @range empty? */ |
| 50 | static inline bool range_is_empty(const Range *range) |
| 51 | { |
| 52 | range_invariant(range); |
| 53 | return range->lob > range->upb; |
| 54 | } |
| 55 | |
| 56 | /* Does @range contain @val? */ |
| 57 | static inline bool range_contains(const Range *range, uint64_t val) |
| 58 | { |
| 59 | return val >= range->lob && val <= range->upb; |
| 60 | } |
| 61 | |
| 62 | /* Initialize @range to the empty range */ |
| 63 | static inline void range_make_empty(Range *range) |
| 64 | { |
| 65 | *range = range_empty; |
| 66 | assert(range_is_empty(range)); |
| 67 | } |
| 68 | |
| 69 | /* |
| 70 | * Initialize @range to span the interval [@lob,@upb]. |
| 71 | * Both bounds are inclusive. |
| 72 | * The interval must not be empty, i.e. @lob must be less than or |
| 73 | * equal @upb. |
| 74 | */ |
| 75 | static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb) |
| 76 | { |
| 77 | range->lob = lob; |
| 78 | range->upb = upb; |
| 79 | assert(!range_is_empty(range)); |
| 80 | } |
| 81 | |
| 82 | /* |
| 83 | * Initialize @range to span the interval [@lob,@upb_plus1). |
| 84 | * The lower bound is inclusive, the upper bound is exclusive. |
| 85 | * Zero @upb_plus1 is special: if @lob is also zero, set @range to the |
| 86 | * empty range. Else, set @range to [@lob,UINT64_MAX]. |
| 87 | */ |
| 88 | static inline void range_set_bounds1(Range *range, |
| 89 | uint64_t lob, uint64_t upb_plus1) |
| 90 | { |
| 91 | if (!lob && !upb_plus1) { |
| 92 | *range = range_empty; |
| 93 | } else { |
| 94 | range->lob = lob; |
| 95 | range->upb = upb_plus1 - 1; |
| 96 | } |
| 97 | range_invariant(range); |
| 98 | } |
| 99 | |
| 100 | /* Return @range's lower bound. @range must not be empty. */ |
| 101 | static inline uint64_t range_lob(Range *range) |
| 102 | { |
| 103 | assert(!range_is_empty(range)); |
| 104 | return range->lob; |
| 105 | } |
| 106 | |
| 107 | /* Return @range's upper bound. @range must not be empty. */ |
| 108 | static inline uint64_t range_upb(Range *range) |
| 109 | { |
| 110 | assert(!range_is_empty(range)); |
| 111 | return range->upb; |
| 112 | } |
| 113 | |
| 114 | /* |
| 115 | * Initialize @range to span the interval [@lob,@lob + @size - 1]. |
| 116 | * @size may be 0. If the range would overflow, returns -ERANGE, otherwise |
| 117 | * 0. |
| 118 | */ |
| 119 | G_GNUC_WARN_UNUSED_RESULT |
| 120 | static inline int range_init(Range *range, uint64_t lob, uint64_t size) |
| 121 | { |
| 122 | if (lob + size < lob) { |
| 123 | return -ERANGE; |
| 124 | } |
| 125 | range->lob = lob; |
| 126 | range->upb = lob + size - 1; |
| 127 | range_invariant(range); |
| 128 | return 0; |
| 129 | } |
| 130 | |
| 131 | /* |
| 132 | * Initialize @range to span the interval [@lob,@lob + @size - 1]. |
| 133 | * @size may be 0. Range must not overflow. |
| 134 | */ |
| 135 | static inline void range_init_nofail(Range *range, uint64_t lob, uint64_t size) |
| 136 | { |
| 137 | range->lob = lob; |
| 138 | range->upb = lob + size - 1; |
| 139 | range_invariant(range); |
| 140 | } |
| 141 | |
| 142 | /* |
| 143 | * Get the size of @range. |
| 144 | */ |
| 145 | static inline uint64_t range_size(const Range *range) |
| 146 | { |
| 147 | return range->upb - range->lob + 1; |
| 148 | } |
| 149 | |
| 150 | /* |
| 151 | * Check if @range1 overlaps with @range2. If one of the ranges is empty, |
| 152 | * the result is always "false". |
| 153 | */ |
| 154 | static inline bool range_overlaps_range(const Range *range1, |
| 155 | const Range *range2) |
| 156 | { |
| 157 | if (range_is_empty(range1) || range_is_empty(range2)) { |
| 158 | return false; |
| 159 | } |
| 160 | return !(range2->upb < range1->lob || range1->upb < range2->lob); |
| 161 | } |
| 162 | |
| 163 | /* |
| 164 | * Check if @range1 contains @range2. If one of the ranges is empty, |
| 165 | * the result is always "false". |
| 166 | */ |
| 167 | static inline bool range_contains_range(const Range *range1, |
| 168 | const Range *range2) |
| 169 | { |
| 170 | if (range_is_empty(range1) || range_is_empty(range2)) { |
| 171 | return false; |
| 172 | } |
| 173 | return range1->lob <= range2->lob && range1->upb >= range2->upb; |
| 174 | } |
| 175 | |
| 176 | /* |
| 177 | * Extend @range to the smallest interval that includes @extend_by, too. |
| 178 | */ |
| 179 | static inline void range_extend(Range *range, Range *extend_by) |
| 180 | { |
| 181 | if (range_is_empty(extend_by)) { |
| 182 | return; |
| 183 | } |
| 184 | if (range_is_empty(range)) { |
| 185 | *range = *extend_by; |
| 186 | return; |
| 187 | } |
| 188 | if (range->lob > extend_by->lob) { |
| 189 | range->lob = extend_by->lob; |
| 190 | } |
| 191 | if (range->upb < extend_by->upb) { |
| 192 | range->upb = extend_by->upb; |
| 193 | } |
| 194 | range_invariant(range); |
| 195 | } |
| 196 | |
| 197 | /* Get last byte of a range from offset + length. |
| 198 | * Undefined for ranges that wrap around 0. */ |
| 199 | static inline uint64_t range_get_last(uint64_t offset, uint64_t len) |
| 200 | { |
| 201 | return offset + len - 1; |
| 202 | } |
| 203 | |
| 204 | /* Check whether a given range covers a given byte. */ |
| 205 | static inline int range_covers_byte(uint64_t offset, uint64_t len, |
| 206 | uint64_t byte) |
| 207 | { |
| 208 | return offset <= byte && byte <= range_get_last(offset, len); |
| 209 | } |
| 210 | |
| 211 | /* Check whether 2 given ranges overlap. |
| 212 | * Undefined if ranges that wrap around 0. */ |
| 213 | static inline bool ranges_overlap(uint64_t first1, uint64_t len1, |
| 214 | uint64_t first2, uint64_t len2) |
| 215 | { |
| 216 | uint64_t last1 = range_get_last(first1, len1); |
| 217 | uint64_t last2 = range_get_last(first2, len2); |
| 218 | |
| 219 | return !(last2 < first1 || last1 < first2); |
| 220 | } |
| 221 | |
| 222 | /* Get highest non-zero bit position of a range */ |
| 223 | static inline int range_get_last_bit(Range *range) |
| 224 | { |
| 225 | if (range_is_empty(range)) { |
| 226 | return -1; |
| 227 | } |
| 228 | return 63 - clz64(range->upb); |
| 229 | } |
| 230 | |
| 231 | /* |
| 232 | * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap. |
| 233 | * Both @a and @b must not be empty. |
| 234 | */ |
| 235 | int range_compare(Range *a, Range *b); |
| 236 | |
| 237 | GList *range_list_insert(GList *list, Range *data); |
| 238 | |
| 239 | /* |
| 240 | * Inverse an array of sorted ranges over the [low, high] span, ie. |
| 241 | * original ranges becomes holes in the newly allocated inv_ranges |
| 242 | */ |
| 243 | void range_inverse_array(GList *in_ranges, |
| 244 | GList **out_ranges, |
| 245 | uint64_t low, uint64_t high); |
| 246 | |
| 247 | #endif |