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 /* 24 * Operations on 64 bit address ranges. 25 * Notes: 26 * - Ranges must not wrap around 0, but can include UINT64_MAX. 27 */ 28 29 struct Range { 30 /* 31 * Do not access members directly, use the functions! 32 * A non-empty range has @lob <= @upb. 33 * An empty range has @lob == @upb + 1. 34 */ 35 uint64_t lob; /* inclusive lower bound */ 36 uint64_t upb; /* inclusive upper bound */ 37 }; 38 39 static inline void range_invariant(const Range *range) 40 { 41 assert(range->lob <= range->upb || range->lob == range->upb + 1); 42 } 43 44 /* Compound literal encoding the empty range */ 45 #define range_empty ((Range){ .lob = 1, .upb = 0 }) 46 47 /* Is @range empty? */ 48 static inline bool range_is_empty(const Range *range) 49 { 50 range_invariant(range); 51 return range->lob > range->upb; 52 } 53 54 /* Does @range contain @val? */ 55 static inline bool range_contains(const Range *range, uint64_t val) 56 { 57 return val >= range->lob && val <= range->upb; 58 } 59 60 /* Initialize @range to the empty range */ 61 static inline void range_make_empty(Range *range) 62 { 63 *range = range_empty; 64 assert(range_is_empty(range)); 65 } 66 67 /* 68 * Initialize @range to span the interval [@lob,@upb]. 69 * Both bounds are inclusive. 70 * The interval must not be empty, i.e. @lob must be less than or 71 * equal @upb. 72 */ 73 static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb) 74 { 75 range->lob = lob; 76 range->upb = upb; 77 assert(!range_is_empty(range)); 78 } 79 80 /* 81 * Initialize @range to span the interval [@lob,@upb_plus1). 82 * The lower bound is inclusive, the upper bound is exclusive. 83 * Zero @upb_plus1 is special: if @lob is also zero, set @range to the 84 * empty range. Else, set @range to [@lob,UINT64_MAX]. 85 */ 86 static inline void range_set_bounds1(Range *range, 87 uint64_t lob, uint64_t upb_plus1) 88 { 89 if (!lob && !upb_plus1) { 90 *range = range_empty; 91 } else { 92 range->lob = lob; 93 range->upb = upb_plus1 - 1; 94 } 95 range_invariant(range); 96 } 97 98 /* Return @range's lower bound. @range must not be empty. */ 99 static inline uint64_t range_lob(Range *range) 100 { 101 assert(!range_is_empty(range)); 102 return range->lob; 103 } 104 105 /* Return @range's upper bound. @range must not be empty. */ 106 static inline uint64_t range_upb(Range *range) 107 { 108 assert(!range_is_empty(range)); 109 return range->upb; 110 } 111 112 /* 113 * Initialize @range to span the interval [@lob,@lob + @size - 1]. 114 * @size may be 0. If the range would overflow, returns -ERANGE, otherwise 115 * 0. 116 */ 117 G_GNUC_WARN_UNUSED_RESULT 118 static inline int range_init(Range *range, uint64_t lob, uint64_t size) 119 { 120 if (lob + size < lob) { 121 return -ERANGE; 122 } 123 range->lob = lob; 124 range->upb = lob + size - 1; 125 range_invariant(range); 126 return 0; 127 } 128 129 /* 130 * Initialize @range to span the interval [@lob,@lob + @size - 1]. 131 * @size may be 0. Range must not overflow. 132 */ 133 static inline void range_init_nofail(Range *range, uint64_t lob, uint64_t size) 134 { 135 range->lob = lob; 136 range->upb = lob + size - 1; 137 range_invariant(range); 138 } 139 140 /* 141 * Get the size of @range. 142 */ 143 static inline uint64_t range_size(const Range *range) 144 { 145 return range->upb - range->lob + 1; 146 } 147 148 /* 149 * Check if @range1 overlaps with @range2. If one of the ranges is empty, 150 * the result is always "false". 151 */ 152 static inline bool range_overlaps_range(const Range *range1, 153 const Range *range2) 154 { 155 if (range_is_empty(range1) || range_is_empty(range2)) { 156 return false; 157 } 158 return !(range2->upb < range1->lob || range1->upb < range2->lob); 159 } 160 161 /* 162 * Check if @range1 contains @range2. If one of the ranges is empty, 163 * the result is always "false". 164 */ 165 static inline bool range_contains_range(const Range *range1, 166 const Range *range2) 167 { 168 if (range_is_empty(range1) || range_is_empty(range2)) { 169 return false; 170 } 171 return range1->lob <= range2->lob && range1->upb >= range2->upb; 172 } 173 174 /* 175 * Extend @range to the smallest interval that includes @extend_by, too. 176 */ 177 static inline void range_extend(Range *range, Range *extend_by) 178 { 179 if (range_is_empty(extend_by)) { 180 return; 181 } 182 if (range_is_empty(range)) { 183 *range = *extend_by; 184 return; 185 } 186 if (range->lob > extend_by->lob) { 187 range->lob = extend_by->lob; 188 } 189 if (range->upb < extend_by->upb) { 190 range->upb = extend_by->upb; 191 } 192 range_invariant(range); 193 } 194 195 /* Get last byte of a range from offset + length. 196 * Undefined for ranges that wrap around 0. */ 197 static inline uint64_t range_get_last(uint64_t offset, uint64_t len) 198 { 199 return offset + len - 1; 200 } 201 202 /* Check whether a given range covers a given byte. */ 203 static inline int range_covers_byte(uint64_t offset, uint64_t len, 204 uint64_t byte) 205 { 206 return offset <= byte && byte <= range_get_last(offset, len); 207 } 208 209 /* Check whether 2 given ranges overlap. 210 * Undefined if ranges that wrap around 0. */ 211 static inline int ranges_overlap(uint64_t first1, uint64_t len1, 212 uint64_t first2, uint64_t len2) 213 { 214 uint64_t last1 = range_get_last(first1, len1); 215 uint64_t last2 = range_get_last(first2, len2); 216 217 return !(last2 < first1 || last1 < first2); 218 } 219 220 /* 221 * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap. 222 * Both @a and @b must not be empty. 223 */ 224 int range_compare(Range *a, Range *b); 225 226 GList *range_list_insert(GList *list, Range *data); 227 228 /* 229 * Inverse an array of sorted ranges over the [low, high] span, ie. 230 * original ranges becomes holes in the newly allocated inv_ranges 231 */ 232 void range_inverse_array(GList *in_ranges, 233 GList **out_ranges, 234 uint64_t low, uint64_t high); 235 236 #endif 237