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
20namespace mojo {
21template <typename T> class Array;
22class String;
23
24namespace internal {
25
26// std::numeric_limits<uint32_t>::max() is not a compile-time constant (until
27// C++11).
28const uint32_t kMaxUint32 = 0xFFFFFFFF;
29
30std::string MakeMessageWithArrayIndex(const char* message,
31                                      size_t size,
32                                      size_t index);
33
34std::string MakeMessageWithExpectedArraySize(const char* message,
35                                             size_t size,
36                                             size_t expected_size);
37
38template <typename T>
39struct 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
59template <typename P>
60struct 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
80template <typename T>
81struct 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.
106template <>
107struct 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.
143template <uint32_t in_expected_num_elements,
144          bool in_element_is_nullable,
145          typename InElementValidateParams>
146class 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.
160class 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
167template <typename T, bool is_handle> struct ArraySerializationHelper;
168
169template <typename T>
170struct 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
196template <>
197struct 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
235template <typename H>
236struct 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
263template <typename P>
264struct 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
326template <typename T>
327class 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};
426MOJO_COMPILE_ASSERT(sizeof(Array_Data<char>) == 8, bad_sizeof_Array_Data);
427
428// UTF-8 encoded
429typedef Array_Data<char> String_Data;
430
431template <typename T, bool kIsMoveOnlyType> struct ArrayTraits {};
432
433template <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
456template <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
504template <> 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