mojo/public/cpp/bindings/lib/array_internal.h

   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(VALIDATION_ERROR_UNEXPECTED_INVALID_HANDLE);
 220         return false;
 221       }
 222       if (!bounds_checker->ClaimHandle(elements[i])) {
 223         ReportValidationError(VALIDATION_ERROR_ILLEGAL_HANDLE);
 224         return false;
 225       }
 226     }
 227     return true;
 228   }
 229 };
 230
 231 template <typename H>
 232 struct ArraySerializationHelper<H, true> {
 233   typedef typename ArrayDataTraits<H>::StorageType ElementType;
 234
 235   static void EncodePointersAndHandles(const ArrayHeader* header,
 236                                        ElementType* elements,
 237                                        std::vector<Handle>* handles) {
 238     ArraySerializationHelper<Handle, true>::EncodePointersAndHandles(
 239         header, elements, handles);
 240   }
 241
 242   static void DecodePointersAndHandles(const ArrayHeader* header,
 243                                        ElementType* elements,
 244                                        std::vector<Handle>* handles) {
 245     ArraySerializationHelper<Handle, true>::DecodePointersAndHandles(
 246         header, elements, handles);
 247   }
 248
 249   template <bool element_is_nullable, typename ElementValidateParams>
 250   static bool ValidateElements(const ArrayHeader* header,
 251                                const ElementType* elements,
 252                                BoundsChecker* bounds_checker) {
 253     return ArraySerializationHelper<Handle, true>::
 254         ValidateElements<element_is_nullable, ElementValidateParams>(
 255             header, elements, bounds_checker);
 256   }
 257 };
 258
 259 template <typename P>
 260 struct ArraySerializationHelper<P*, false> {
 261   typedef typename ArrayDataTraits<P*>::StorageType ElementType;
 262
 263   static void EncodePointersAndHandles(const ArrayHeader* header,
 264                                        ElementType* elements,
 265                                        std::vector<Handle>* handles) {
 266     for (uint32_t i = 0; i < header->num_elements; ++i)
 267       Encode(&elements[i], handles);
 268   }
 269
 270   static void DecodePointersAndHandles(const ArrayHeader* header,
 271                                        ElementType* elements,
 272                                        std::vector<Handle>* handles) {
 273     for (uint32_t i = 0; i < header->num_elements; ++i)
 274       Decode(&elements[i], handles);
 275   }
 276
 277   template <bool element_is_nullable, typename ElementValidateParams>
 278   static bool ValidateElements(const ArrayHeader* header,
 279                                const ElementType* elements,
 280                                BoundsChecker* bounds_checker) {
 281     for (uint32_t i = 0; i < header->num_elements; ++i) {
 282       if (!element_is_nullable && !elements[i].offset) {
 283         ReportValidationError(VALIDATION_ERROR_UNEXPECTED_NULL_POINTER);
 284         return false;
 285       }
 286       if (!ValidateEncodedPointer(&elements[i].offset)) {
 287         ReportValidationError(VALIDATION_ERROR_ILLEGAL_POINTER);
 288         return false;
 289       }
 290       if (!ValidateCaller<P, ElementValidateParams>::Run(
 291               DecodePointerRaw(&elements[i].offset), bounds_checker)) {
 292         return false;
 293       }
 294     }
 295     return true;
 296   }
 297
 298  private:
 299   template <typename T, typename Params>
 300   struct ValidateCaller {
 301     static bool Run(const void* data, BoundsChecker* bounds_checker) {
 302       MOJO_COMPILE_ASSERT(
 303           (IsSame<Params, NoValidateParams>::value),
 304           Struct_type_should_not_have_array_validate_params);
 305
 306       return T::Validate(data, bounds_checker);
 307     }
 308   };
 309
 310   template <typename T, typename Params>
 311   struct ValidateCaller<Array_Data<T>, Params> {
 312     static bool Run(const void* data, BoundsChecker* bounds_checker) {
 313       return Array_Data<T>::template Validate<Params>(data, bounds_checker);
 314     }
 315   };
 316 };
 317
 318 template <typename T>
 319 class Array_Data {
 320  public:
 321   typedef ArrayDataTraits<T> Traits;
 322   typedef typename Traits::StorageType StorageType;
 323   typedef typename Traits::Ref Ref;
 324   typedef typename Traits::ConstRef ConstRef;
 325   typedef ArraySerializationHelper<T, IsHandle<T>::value> Helper;
 326
 327   // Returns NULL if |num_elements| or the corresponding storage size cannot be
 328   // stored in uint32_t.
 329   static Array_Data<T>* New(size_t num_elements, Buffer* buf) {
 330     if (num_elements > Traits::kMaxNumElements)
 331       return NULL;
 332
 333     uint32_t num_bytes =
 334         Traits::GetStorageSize(static_cast<uint32_t>(num_elements));
 335     return new (buf->Allocate(num_bytes)) Array_Data<T>(
 336         num_bytes, static_cast<uint32_t>(num_elements));
 337   }
 338
 339   template <typename Params>
 340   static bool Validate(const void* data, BoundsChecker* bounds_checker) {
 341     if (!data)
 342       return true;
 343     if (!IsAligned(data)) {
 344       ReportValidationError(VALIDATION_ERROR_MISALIGNED_OBJECT);
 345       return false;
 346     }
 347     if (!bounds_checker->IsValidRange(data, sizeof(ArrayHeader))) {
 348       ReportValidationError(VALIDATION_ERROR_ILLEGAL_MEMORY_RANGE);
 349       return false;
 350     }
 351     const ArrayHeader* header = static_cast<const ArrayHeader*>(data);
 352     if (header->num_elements > Traits::kMaxNumElements ||
 353         header->num_bytes < Traits::GetStorageSize(header->num_elements)) {
 354       ReportValidationError(VALIDATION_ERROR_UNEXPECTED_ARRAY_HEADER);
 355       return false;
 356     }
 357     if (Params::expected_num_elements != 0 &&
 358         header->num_elements != Params::expected_num_elements) {
 359       ReportValidationError(VALIDATION_ERROR_UNEXPECTED_ARRAY_HEADER);
 360       return false;
 361     }
 362     if (!bounds_checker->ClaimMemory(data, header->num_bytes)) {
 363       ReportValidationError(VALIDATION_ERROR_ILLEGAL_MEMORY_RANGE);
 364       return false;
 365     }
 366
 367     const Array_Data<T>* object = static_cast<const Array_Data<T>*>(data);
 368     return Helper::template ValidateElements<
 369         Params::element_is_nullable, typename Params::ElementValidateParams>(
 370             &object->header_, object->storage(), bounds_checker);
 371   }
 372
 373   size_t size() const { return header_.num_elements; }
 374
 375   Ref at(size_t offset) {
 376     MOJO_DCHECK(offset < static_cast<size_t>(header_.num_elements));
 377     return Traits::ToRef(storage(), offset);
 378   }
 379
 380   ConstRef at(size_t offset) const {
 381     MOJO_DCHECK(offset < static_cast<size_t>(header_.num_elements));
 382     return Traits::ToConstRef(storage(), offset);
 383   }
 384
 385   StorageType* storage() {
 386     return reinterpret_cast<StorageType*>(
 387         reinterpret_cast<char*>(this) + sizeof(*this));
 388   }
 389
 390   const StorageType* storage() const {
 391     return reinterpret_cast<const StorageType*>(
 392         reinterpret_cast<const char*>(this) + sizeof(*this));
 393   }
 394
 395   void EncodePointersAndHandles(std::vector<Handle>* handles) {
 396     Helper::EncodePointersAndHandles(&header_, storage(), handles);
 397   }
 398
 399   void DecodePointersAndHandles(std::vector<Handle>* handles) {
 400     Helper::DecodePointersAndHandles(&header_, storage(), handles);
 401   }
 402
 403  private:
 404   Array_Data(uint32_t num_bytes, uint32_t num_elements) {
 405     header_.num_bytes = num_bytes;
 406     header_.num_elements = num_elements;
 407   }
 408   ~Array_Data() {}
 409
 410   internal::ArrayHeader header_;
 411
 412   // Elements of type internal::ArrayDataTraits<T>::StorageType follow.
 413 };
 414 MOJO_COMPILE_ASSERT(sizeof(Array_Data<char>) == 8, bad_sizeof_Array_Data);
 415
 416 // UTF-8 encoded
 417 typedef Array_Data<char> String_Data;
 418
 419 template <typename T, bool kIsMoveOnlyType> struct ArrayTraits {};
 420
 421 template <typename T> struct ArrayTraits<T, false> {
 422   typedef T StorageType;
 423   typedef typename std::vector<T>::reference RefType;
 424   typedef typename std::vector<T>::const_reference ConstRefType;
 425   typedef ConstRefType ForwardType;
 426   static inline void Initialize(std::vector<T>* vec) {
 427   }
 428   static inline void Finalize(std::vector<T>* vec) {
 429   }
 430   static inline ConstRefType at(const std::vector<T>* vec, size_t offset) {
 431     return vec->at(offset);
 432   }
 433   static inline RefType at(std::vector<T>* vec, size_t offset) {
 434     return vec->at(offset);
 435   }
 436   static inline void Resize(std::vector<T>* vec, size_t size) {
 437     vec->resize(size);
 438   }
 439   static inline void PushBack(std::vector<T>* vec, ForwardType value) {
 440     vec->push_back(value);
 441   }
 442 };
 443
 444 template <typename T> struct ArrayTraits<T, true> {
 445   struct StorageType {
 446     char buf[sizeof(T) + (8 - (sizeof(T) % 8)) % 8];  // Make 8-byte aligned.
 447   };
 448   typedef T& RefType;
 449   typedef const T& ConstRefType;
 450   typedef T ForwardType;
 451   static inline void Initialize(std::vector<StorageType>* vec) {
 452     for (size_t i = 0; i < vec->size(); ++i)
 453       new (vec->at(i).buf) T();
 454   }
 455   static inline void Finalize(std::vector<StorageType>* vec) {
 456     for (size_t i = 0; i < vec->size(); ++i)
 457       reinterpret_cast<T*>(vec->at(i).buf)->~T();
 458   }
 459   static inline ConstRefType at(const std::vector<StorageType>* vec,
 460                                 size_t offset) {
 461     return *reinterpret_cast<const T*>(vec->at(offset).buf);
 462   }
 463   static inline RefType at(std::vector<StorageType>* vec, size_t offset) {
 464     return *reinterpret_cast<T*>(vec->at(offset).buf);
 465   }
 466   static inline void Resize(std::vector<StorageType>* vec, size_t size) {
 467     size_t old_size = vec->size();
 468     for (size_t i = size; i < old_size; i++)
 469       reinterpret_cast<T*>(vec->at(i).buf)->~T();
 470     ResizeStorage(vec, size);
 471     for (size_t i = old_size; i < vec->size(); i++)
 472       new (vec->at(i).buf) T();
 473   }
 474   static inline void PushBack(std::vector<StorageType>* vec, RefType value) {
 475     size_t old_size = vec->size();
 476     ResizeStorage(vec, old_size + 1);
 477     new (vec->at(old_size).buf) T(value.Pass());
 478   }
 479   static inline void ResizeStorage(std::vector<StorageType>* vec, size_t size) {
 480     if (size <= vec->capacity()) {
 481       vec->resize(size);
 482       return;
 483     }
 484     std::vector<StorageType> new_storage(size);
 485     for (size_t i = 0; i < vec->size(); i++)
 486       new (new_storage.at(i).buf) T(at(vec, i).Pass());
 487     vec->swap(new_storage);
 488     Finalize(&new_storage);
 489   }
 490 };
 491
 492 template <> struct WrapperTraits<String, false> {
 493   typedef String_Data* DataType;
 494 };
 495
 496 }  // namespace internal
 497 }  // namespace mojo
 498
 499 #endif  // MOJO_PUBLIC_CPP_BINDINGS_LIB_ARRAY_INTERNAL_H_