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 | static inline int QEMU_WARN_UNUSED_RESULT range_init(Range *range, uint64_t lob, |
118 | 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 | GList *range_list_insert(GList *list, Range *data); |
221 | |
222 | #endif |
223 | |