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(
 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_