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 int 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 248