1 /*
2 * Copyright 2018 Google LLC
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /**
18 * This file defines safe operations related to bounds checking and size
19 * calculations - robust against overflow, etc.
20 */
21
22 #ifndef FCP_BASE_BOUNDS_H_
23 #define FCP_BASE_BOUNDS_H_
24
25 #include <limits>
26 #include <type_traits>
27
28 #include "fcp/base/monitoring.h"
29
30 namespace fcp {
31
32 /**
33 * Attempts to cast 'from' to 'To'. Returns true (and sets *to) if the cast is
34 * lossless; otherwise, returns false without modifying *to.
35 *
36 * Examples:
37 * TryCastInteger<uint8_t, uint32_t>(1024, &to) => false
38 * static_cast<uint8_t>(1024) would yield 0
39 * TryCastInteger<uint8_t, uint32_t>(123, &to) => true
40 * TryCastInteger<uint32_t, int32_t>(123, &to) => true
41 * TryCastInteger<uint32_t, int32_t>(-1, &to) => false
42 */
43 template <typename To, typename From>
TryCastInteger(From from,To * to)44 bool TryCastInteger(From from, To* to) {
45 static_assert(std::is_integral<To>::value && std::is_integral<From>::value,
46 "Both types must be integral");
47
48 if (std::is_signed<From>::value == std::is_signed<To>::value) {
49 // Same sign: Easy!
50 if (from < std::numeric_limits<To>::min() ||
51 from > std::numeric_limits<To>::max()) {
52 return false;
53 }
54 } else if (std::is_signed<From>::value && !std::is_signed<To>::value) {
55 // Signed => Unsigned: Widening conversion would sign-extend 'from' first;
56 // i.e. -1 would look larger than To's min(). Negative values are definitely
57 // out of range anyway. Positive values are effectively zero-extended,
58 // which is fine.
59 if (from < 0 || from > std::numeric_limits<To>::max()) {
60 return false;
61 }
62 } else {
63 // Unsigned => Signed: We don't want to mention min(), since widening
64 // conversion of min() would have the same problem as in the prior case.
65 if (from > std::numeric_limits<To>::max()) {
66 return false;
67 }
68 }
69
70 *to = static_cast<To>(from);
71 return true;
72 }
73
74 /**
75 * Casts from 'from' to 'To'. Check-fails if the cast is not lossless.
76 * See also: TryCastInteger
77 */
78 template <typename To, typename From>
CastIntegerChecked(From from)79 To CastIntegerChecked(From from) {
80 To to;
81 FCP_CHECK(TryCastInteger(from, &to));
82 return to;
83 }
84
85 /** Multiplies without the possibility of overflow. */
SafeMultiply(uint32_t a,uint32_t b)86 inline uint64_t SafeMultiply(uint32_t a, uint32_t b) {
87 return static_cast<uint64_t>(a) * static_cast<uint64_t>(b);
88 }
89
90 /**
91 * Represents an embedded address space as a pair of a starting address and a
92 * size. This is a correspondence of the addresses [0, size) <=> [start, start +
93 * size), for the embedded address space and this one, respectively.
94 *
95 * A ForeignPointer represents an address in an embedded address space (left).
96 * Given a ForeignPointer and a supposed size, one can use
97 * MapOutOfAddressSpace() to get a pointer in this address space (right),
98 * subject to bounds checking.
99 *
100 * We require that start + size does not overflow; this is convenient for bounds
101 * checks. Since start + size is the open part of the interval (one past the
102 * end), that happens to mean that ~0 cannot be in bounds (irrelevant in
103 * practice).
104 */
105 struct AddressSpace {
106 void* start;
107 uint64_t size;
108
109 /**
110 * Returns a representation of the ambient, 'native' address space - it just
111 * starts at address zero and has maximum size. Note that the highest address
112 * (~0) is thus out of bounds.
113 */
CurrentAddressSpace114 static constexpr AddressSpace Current() {
115 return AddressSpace{nullptr, ~static_cast<uint64_t>(0)};
116 }
117
118 /**
119 * Returns an AddressSpace spanning mapping [0, size) <=> [start, start +
120 * size).
121 */
EmbeddedAddressSpace122 static AddressSpace Embedded(void* start, uint64_t size) {
123 uint64_t end;
124 FCP_CHECK(
125 !__builtin_add_overflow(reinterpret_cast<uint64_t>(start), size, &end));
126 return AddressSpace{start, size};
127 }
128 };
129
130 /**
131 * An address in some AddressSpace. It can be translated to a pointer in this
132 * address space with MapOutOfAddressSpace().
133 */
134 struct ForeignPointer {
135 uint64_t value;
136 };
137
138 /**
139 * Translates a ForeignPointer out of an embedded AddressSpace, yielding a void*
140 * in this address space. The pointer is understood to refer to (size * count)
141 * bytes of memory (i.e. an array), as useful pointers tend to do.
142 *
143 * If that span does _not_ fully reside within the provided AddressSpace,
144 * returns nullptr. Otherwise, returns space.start + ptr.value.
145 *
146 * This function is intended to behave safely for arbitrary values of 'ptr',
147 * 'size', and 'count', perhaps provided by untrusted code. 'size' and 'count'
148 * are provided separately for this reason (to save the caller from worrying
149 * about multiplication overflow).
150 */
MapOutOfAddressSpace(AddressSpace const & space,ForeignPointer ptr,uint32_t size,uint32_t count)151 inline void* MapOutOfAddressSpace(AddressSpace const& space, ForeignPointer ptr,
152 uint32_t size, uint32_t count) {
153 // Because the element size and count are each 32 bits, we can't overflow a 64
154 // bit total_size.
155 uint64_t total_size = SafeMultiply(size, count);
156
157 // The span in the embedded space is [ptr, ptr + total_size).
158 uint64_t ptr_end;
159 if (__builtin_add_overflow(ptr.value, total_size, &ptr_end)) {
160 return nullptr;
161 }
162
163 // The embedded address space ranges from [0, space.size). We know that ptr >=
164 // 0 and that ptr <= ptr_end, so it is sufficient to check that ptr_end <=
165 // space.size. Note that this allows ptr == space.size, iff total_size == 0.
166 if (ptr_end > space.size) {
167 return nullptr;
168 }
169
170 // AddressSpace requires that start + size does not overflow.
171 // - Since ptr_end <= space.size, space.start + ptr_end does not overflow.
172 // - Since ptr <= ptr_end, space.start + ptr does not overflow.
173 // Therefore, we can return the offset span space.start + [ptr, ptr_end).
174 return reinterpret_cast<void*>(reinterpret_cast<uint64_t>(space.start) +
175 ptr.value);
176 }
177
178 } // namespace fcp
179
180 #endif // FCP_BASE_BOUNDS_H_
181