1 // Copyright 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef MOJO_PUBLIC_CPP_BINDINGS_LIB_ARRAY_INTERNAL_H_ 6 #define MOJO_PUBLIC_CPP_BINDINGS_LIB_ARRAY_INTERNAL_H_ 7 8 #include <new> 9 #include <vector> 10 11 #include "mojo/public/c/system/macros.h" 12 #include "mojo/public/cpp/bindings/lib/bindings_internal.h" 13 #include "mojo/public/cpp/bindings/lib/bindings_serialization.h" 14 #include "mojo/public/cpp/bindings/lib/bounds_checker.h" 15 #include "mojo/public/cpp/bindings/lib/buffer.h" 16 #include "mojo/public/cpp/bindings/lib/template_util.h" 17 #include "mojo/public/cpp/bindings/lib/validation_errors.h" 18 #include "mojo/public/cpp/environment/logging.h" 19 20 namespace mojo { 21 template <typename T> class Array; 22 class String; 23 24 namespace internal { 25 26 // std::numeric_limits<uint32_t>::max() is not a compile-time constant (until 27 // C++11). 28 const uint32_t kMaxUint32 = 0xFFFFFFFF; 29 30 std::string MakeMessageWithArrayIndex(const char* message, 31 size_t size, 32 size_t index); 33 34 std::string MakeMessageWithExpectedArraySize(const char* message, 35 size_t size, 36 size_t expected_size); 37 38 template <typename T> 39 struct ArrayDataTraits { 40 typedef T StorageType; 41 typedef T& Ref; 42 typedef T const& ConstRef; 43 44 static const uint32_t kMaxNumElements = 45 (kMaxUint32 - sizeof(ArrayHeader)) / sizeof(StorageType); 46 47 static uint32_t GetStorageSize(uint32_t num_elements) { 48 MOJO_DCHECK(num_elements <= kMaxNumElements); 49 return sizeof(ArrayHeader) + sizeof(StorageType) * num_elements; 50 } 51 static Ref ToRef(StorageType* storage, size_t offset) { 52 return storage[offset]; 53 } 54 static ConstRef ToConstRef(const StorageType* storage, size_t offset) { 55 return storage[offset]; 56 } 57 }; 58 59 template <typename P> 60 struct ArrayDataTraits<P*> { 61 typedef StructPointer<P> StorageType; 62 typedef P*& Ref; 63 typedef P* const& ConstRef; 64 65 static const uint32_t kMaxNumElements = 66 (kMaxUint32 - sizeof(ArrayHeader)) / sizeof(StorageType); 67 68 static uint32_t GetStorageSize(uint32_t num_elements) { 69 MOJO_DCHECK(num_elements <= kMaxNumElements); 70 return sizeof(ArrayHeader) + sizeof(StorageType) * num_elements; 71 } 72 static Ref ToRef(StorageType* storage, size_t offset) { 73 return storage[offset].ptr; 74 } 75 static ConstRef ToConstRef(const StorageType* storage, size_t offset) { 76 return storage[offset].ptr; 77 } 78 }; 79 80 template <typename T> 81 struct ArrayDataTraits<Array_Data<T>*> { 82 typedef ArrayPointer<T> StorageType; 83 typedef Array_Data<T>*& Ref; 84 typedef Array_Data<T>* const& ConstRef; 85 86 static const uint32_t kMaxNumElements = 87 (kMaxUint32 - sizeof(ArrayHeader)) / sizeof(StorageType); 88 89 static uint32_t GetStorageSize(uint32_t num_elements) { 90 MOJO_DCHECK(num_elements <= kMaxNumElements); 91 return sizeof(ArrayHeader) + sizeof(StorageType) * num_elements; 92 } 93 static Ref ToRef(StorageType* storage, size_t offset) { 94 return storage[offset].ptr; 95 } 96 static ConstRef ToConstRef(const StorageType* storage, size_t offset) { 97 return storage[offset].ptr; 98 } 99 }; 100 101 // Specialization of Arrays for bools, optimized for space. It has the 102 // following differences from a generalized Array: 103 // * Each element takes up a single bit of memory. 104 // * Accessing a non-const single element uses a helper class |BitRef|, which 105 // emulates a reference to a bool. 106 template <> 107 struct ArrayDataTraits<bool> { 108 // Helper class to emulate a reference to a bool, used for direct element 109 // access. 110 class BitRef { 111 public: 112 ~BitRef(); 113 BitRef& operator=(bool value); 114 BitRef& operator=(const BitRef& value); 115 operator bool() const; 116 private: 117 friend struct ArrayDataTraits<bool>; 118 BitRef(uint8_t* storage, uint8_t mask); 119 BitRef(); 120 uint8_t* storage_; 121 uint8_t mask_; 122 }; 123 124 // Because each element consumes only 1/8 byte. 125 static const uint32_t kMaxNumElements = kMaxUint32; 126 127 typedef uint8_t StorageType; 128 typedef BitRef Ref; 129 typedef bool ConstRef; 130 131 static uint32_t GetStorageSize(uint32_t num_elements) { 132 return sizeof(ArrayHeader) + ((num_elements + 7) / 8); 133 } 134 static BitRef ToRef(StorageType* storage, size_t offset) { 135 return BitRef(&storage[offset / 8], 1 << (offset % 8)); 136 } 137 static bool ToConstRef(const StorageType* storage, size_t offset) { 138 return (storage[offset / 8] & (1 << (offset % 8))) != 0; 139 } 140 }; 141 142 // Array type information needed for valdiation. 143 template <uint32_t in_expected_num_elements, 144 bool in_element_is_nullable, 145 typename InElementValidateParams> 146 class ArrayValidateParams { 147 public: 148 // Validation information for elements. It is either another specialization of 149 // ArrayValidateParams (if elements are arrays) or NoValidateParams. 150 typedef InElementValidateParams ElementValidateParams; 151 152 // If |expected_num_elements| is not 0, the array is expected to have exactly 153 // that number of elements. 154 static const uint32_t expected_num_elements = in_expected_num_elements; 155 // Whether the elements are nullable. 156 static const bool element_is_nullable = in_element_is_nullable; 157 }; 158 159 // NoValidateParams is used to indicate the end of an ArrayValidateParams chain. 160 class NoValidateParams { 161 }; 162 163 // What follows is code to support the serialization of Array_Data<T>. There 164 // are two interesting cases: arrays of primitives and arrays of objects. 165 // Arrays of objects are represented as arrays of pointers to objects. 166 167 template <typename T, bool is_handle> struct ArraySerializationHelper; 168 169 template <typename T> 170 struct ArraySerializationHelper<T, false> { 171 typedef typename ArrayDataTraits<T>::StorageType ElementType; 172 173 static void EncodePointersAndHandles(const ArrayHeader* header, 174 ElementType* elements, 175 std::vector<Handle>* handles) { 176 } 177 178 static void DecodePointersAndHandles(const ArrayHeader* header, 179 ElementType* elements, 180 std::vector<Handle>* handles) { 181 } 182 183 template <bool element_is_nullable, typename ElementValidateParams> 184 static bool ValidateElements(const ArrayHeader* header, 185 const ElementType* elements, 186 BoundsChecker* bounds_checker) { 187 MOJO_COMPILE_ASSERT(!element_is_nullable, 188 Primitive_type_should_be_non_nullable); 189 MOJO_COMPILE_ASSERT( 190 (IsSame<ElementValidateParams, NoValidateParams>::value), 191 Primitive_type_should_not_have_array_validate_params); 192 return true; 193 } 194 }; 195 196 template <> 197 struct ArraySerializationHelper<Handle, true> { 198 typedef ArrayDataTraits<Handle>::StorageType ElementType; 199 200 static void EncodePointersAndHandles(const ArrayHeader* header, 201 ElementType* elements, 202 std::vector<Handle>* handles); 203 204 static void DecodePointersAndHandles(const ArrayHeader* header, 205 ElementType* elements, 206 std::vector<Handle>* handles); 207 208 template <bool element_is_nullable, typename ElementValidateParams> 209 static bool ValidateElements(const ArrayHeader* header, 210 const ElementType* elements, 211 BoundsChecker* bounds_checker) { 212 MOJO_COMPILE_ASSERT( 213 (IsSame<ElementValidateParams, NoValidateParams>::value), 214 Handle_type_should_not_have_array_validate_params); 215 216 for (uint32_t i = 0; i < header->num_elements; ++i) { 217 if (!element_is_nullable && 218 elements[i].value() == kEncodedInvalidHandleValue) { 219 ReportValidationError( 220 VALIDATION_ERROR_UNEXPECTED_INVALID_HANDLE, 221 MakeMessageWithArrayIndex( 222 "invalid handle in array expecting valid handles", 223 header->num_elements, i).c_str()); 224 return false; 225 } 226 if (!bounds_checker->ClaimHandle(elements[i])) { 227 ReportValidationError(VALIDATION_ERROR_ILLEGAL_HANDLE); 228 return false; 229 } 230 } 231 return true; 232 } 233 }; 234 235 template <typename H> 236 struct ArraySerializationHelper<H, true> { 237 typedef typename ArrayDataTraits<H>::StorageType ElementType; 238 239 static void EncodePointersAndHandles(const ArrayHeader* header, 240 ElementType* elements, 241 std::vector<Handle>* handles) { 242 ArraySerializationHelper<Handle, true>::EncodePointersAndHandles( 243 header, elements, handles); 244 } 245 246 static void DecodePointersAndHandles(const ArrayHeader* header, 247 ElementType* elements, 248 std::vector<Handle>* handles) { 249 ArraySerializationHelper<Handle, true>::DecodePointersAndHandles( 250 header, elements, handles); 251 } 252 253 template <bool element_is_nullable, typename ElementValidateParams> 254 static bool ValidateElements(const ArrayHeader* header, 255 const ElementType* elements, 256 BoundsChecker* bounds_checker) { 257 return ArraySerializationHelper<Handle, true>:: 258 ValidateElements<element_is_nullable, ElementValidateParams>( 259 header, elements, bounds_checker); 260 } 261 }; 262 263 template <typename P> 264 struct ArraySerializationHelper<P*, false> { 265 typedef typename ArrayDataTraits<P*>::StorageType ElementType; 266 267 static void EncodePointersAndHandles(const ArrayHeader* header, 268 ElementType* elements, 269 std::vector<Handle>* handles) { 270 for (uint32_t i = 0; i < header->num_elements; ++i) 271 Encode(&elements[i], handles); 272 } 273 274 static void DecodePointersAndHandles(const ArrayHeader* header, 275 ElementType* elements, 276 std::vector<Handle>* handles) { 277 for (uint32_t i = 0; i < header->num_elements; ++i) 278 Decode(&elements[i], handles); 279 } 280 281 template <bool element_is_nullable, typename ElementValidateParams> 282 static bool ValidateElements(const ArrayHeader* header, 283 const ElementType* elements, 284 BoundsChecker* bounds_checker) { 285 for (uint32_t i = 0; i < header->num_elements; ++i) { 286 if (!element_is_nullable && !elements[i].offset) { 287 ReportValidationError( 288 VALIDATION_ERROR_UNEXPECTED_NULL_POINTER, 289 MakeMessageWithArrayIndex( 290 "null in array expecting valid pointers", 291 header->num_elements, i).c_str()); 292 return false; 293 } 294 if (!ValidateEncodedPointer(&elements[i].offset)) { 295 ReportValidationError(VALIDATION_ERROR_ILLEGAL_POINTER); 296 return false; 297 } 298 if (!ValidateCaller<P, ElementValidateParams>::Run( 299 DecodePointerRaw(&elements[i].offset), bounds_checker)) { 300 return false; 301 } 302 } 303 return true; 304 } 305 306 private: 307 template <typename T, typename Params> 308 struct ValidateCaller { 309 static bool Run(const void* data, BoundsChecker* bounds_checker) { 310 MOJO_COMPILE_ASSERT( 311 (IsSame<Params, NoValidateParams>::value), 312 Struct_type_should_not_have_array_validate_params); 313 314 return T::Validate(data, bounds_checker); 315 } 316 }; 317 318 template <typename T, typename Params> 319 struct ValidateCaller<Array_Data<T>, Params> { 320 static bool Run(const void* data, BoundsChecker* bounds_checker) { 321 return Array_Data<T>::template Validate<Params>(data, bounds_checker); 322 } 323 }; 324 }; 325 326 template <typename T> 327 class Array_Data { 328 public: 329 typedef ArrayDataTraits<T> Traits; 330 typedef typename Traits::StorageType StorageType; 331 typedef typename Traits::Ref Ref; 332 typedef typename Traits::ConstRef ConstRef; 333 typedef ArraySerializationHelper<T, IsHandle<T>::value> Helper; 334 335 // Returns NULL if |num_elements| or the corresponding storage size cannot be 336 // stored in uint32_t. 337 static Array_Data<T>* New(size_t num_elements, Buffer* buf) { 338 if (num_elements > Traits::kMaxNumElements) 339 return NULL; 340 341 uint32_t num_bytes = 342 Traits::GetStorageSize(static_cast<uint32_t>(num_elements)); 343 return new (buf->Allocate(num_bytes)) Array_Data<T>( 344 num_bytes, static_cast<uint32_t>(num_elements)); 345 } 346 347 template <typename Params> 348 static bool Validate(const void* data, BoundsChecker* bounds_checker) { 349 if (!data) 350 return true; 351 if (!IsAligned(data)) { 352 ReportValidationError(VALIDATION_ERROR_MISALIGNED_OBJECT); 353 return false; 354 } 355 if (!bounds_checker->IsValidRange(data, sizeof(ArrayHeader))) { 356 ReportValidationError(VALIDATION_ERROR_ILLEGAL_MEMORY_RANGE); 357 return false; 358 } 359 const ArrayHeader* header = static_cast<const ArrayHeader*>(data); 360 if (header->num_elements > Traits::kMaxNumElements || 361 header->num_bytes < Traits::GetStorageSize(header->num_elements)) { 362 ReportValidationError(VALIDATION_ERROR_UNEXPECTED_ARRAY_HEADER); 363 return false; 364 } 365 if (Params::expected_num_elements != 0 && 366 header->num_elements != Params::expected_num_elements) { 367 ReportValidationError( 368 VALIDATION_ERROR_UNEXPECTED_ARRAY_HEADER, 369 MakeMessageWithExpectedArraySize( 370 "fixed-size array has wrong number of elements", 371 header->num_elements, Params::expected_num_elements).c_str()); 372 return false; 373 } 374 if (!bounds_checker->ClaimMemory(data, header->num_bytes)) { 375 ReportValidationError(VALIDATION_ERROR_ILLEGAL_MEMORY_RANGE); 376 return false; 377 } 378 379 const Array_Data<T>* object = static_cast<const Array_Data<T>*>(data); 380 return Helper::template ValidateElements< 381 Params::element_is_nullable, typename Params::ElementValidateParams>( 382 &object->header_, object->storage(), bounds_checker); 383 } 384 385 size_t size() const { return header_.num_elements; } 386 387 Ref at(size_t offset) { 388 MOJO_DCHECK(offset < static_cast<size_t>(header_.num_elements)); 389 return Traits::ToRef(storage(), offset); 390 } 391 392 ConstRef at(size_t offset) const { 393 MOJO_DCHECK(offset < static_cast<size_t>(header_.num_elements)); 394 return Traits::ToConstRef(storage(), offset); 395 } 396 397 StorageType* storage() { 398 return reinterpret_cast<StorageType*>( 399 reinterpret_cast<char*>(this) + sizeof(*this)); 400 } 401 402 const StorageType* storage() const { 403 return reinterpret_cast<const StorageType*>( 404 reinterpret_cast<const char*>(this) + sizeof(*this)); 405 } 406 407 void EncodePointersAndHandles(std::vector<Handle>* handles) { 408 Helper::EncodePointersAndHandles(&header_, storage(), handles); 409 } 410 411 void DecodePointersAndHandles(std::vector<Handle>* handles) { 412 Helper::DecodePointersAndHandles(&header_, storage(), handles); 413 } 414 415 private: 416 Array_Data(uint32_t num_bytes, uint32_t num_elements) { 417 header_.num_bytes = num_bytes; 418 header_.num_elements = num_elements; 419 } 420 ~Array_Data() {} 421 422 internal::ArrayHeader header_; 423 424 // Elements of type internal::ArrayDataTraits<T>::StorageType follow. 425 }; 426 MOJO_COMPILE_ASSERT(sizeof(Array_Data<char>) == 8, bad_sizeof_Array_Data); 427 428 // UTF-8 encoded 429 typedef Array_Data<char> String_Data; 430 431 template <typename T, bool kIsMoveOnlyType> struct ArrayTraits {}; 432 433 template <typename T> struct ArrayTraits<T, false> { 434 typedef T StorageType; 435 typedef typename std::vector<T>::reference RefType; 436 typedef typename std::vector<T>::const_reference ConstRefType; 437 typedef ConstRefType ForwardType; 438 static inline void Initialize(std::vector<T>* vec) { 439 } 440 static inline void Finalize(std::vector<T>* vec) { 441 } 442 static inline ConstRefType at(const std::vector<T>* vec, size_t offset) { 443 return vec->at(offset); 444 } 445 static inline RefType at(std::vector<T>* vec, size_t offset) { 446 return vec->at(offset); 447 } 448 static inline void Resize(std::vector<T>* vec, size_t size) { 449 vec->resize(size); 450 } 451 static inline void PushBack(std::vector<T>* vec, ForwardType value) { 452 vec->push_back(value); 453 } 454 }; 455 456 template <typename T> struct ArrayTraits<T, true> { 457 struct StorageType { 458 char buf[sizeof(T) + (8 - (sizeof(T) % 8)) % 8]; // Make 8-byte aligned. 459 }; 460 typedef T& RefType; 461 typedef const T& ConstRefType; 462 typedef T ForwardType; 463 static inline void Initialize(std::vector<StorageType>* vec) { 464 for (size_t i = 0; i < vec->size(); ++i) 465 new (vec->at(i).buf) T(); 466 } 467 static inline void Finalize(std::vector<StorageType>* vec) { 468 for (size_t i = 0; i < vec->size(); ++i) 469 reinterpret_cast<T*>(vec->at(i).buf)->~T(); 470 } 471 static inline ConstRefType at(const std::vector<StorageType>* vec, 472 size_t offset) { 473 return *reinterpret_cast<const T*>(vec->at(offset).buf); 474 } 475 static inline RefType at(std::vector<StorageType>* vec, size_t offset) { 476 return *reinterpret_cast<T*>(vec->at(offset).buf); 477 } 478 static inline void Resize(std::vector<StorageType>* vec, size_t size) { 479 size_t old_size = vec->size(); 480 for (size_t i = size; i < old_size; i++) 481 reinterpret_cast<T*>(vec->at(i).buf)->~T(); 482 ResizeStorage(vec, size); 483 for (size_t i = old_size; i < vec->size(); i++) 484 new (vec->at(i).buf) T(); 485 } 486 static inline void PushBack(std::vector<StorageType>* vec, RefType value) { 487 size_t old_size = vec->size(); 488 ResizeStorage(vec, old_size + 1); 489 new (vec->at(old_size).buf) T(value.Pass()); 490 } 491 static inline void ResizeStorage(std::vector<StorageType>* vec, size_t size) { 492 if (size <= vec->capacity()) { 493 vec->resize(size); 494 return; 495 } 496 std::vector<StorageType> new_storage(size); 497 for (size_t i = 0; i < vec->size(); i++) 498 new (new_storage.at(i).buf) T(at(vec, i).Pass()); 499 vec->swap(new_storage); 500 Finalize(&new_storage); 501 } 502 }; 503 504 template <> struct WrapperTraits<String, false> { 505 typedef String_Data* DataType; 506 }; 507 508 } // namespace internal 509 } // namespace mojo 510 511 #endif // MOJO_PUBLIC_CPP_BINDINGS_LIB_ARRAY_INTERNAL_H_ 512