dyld3/Array.h

   1 /*
   2  * Copyright (c) 2017 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #ifndef Array_h
  25 #define Array_h
  26
  27 #include <algorithm>
  28 #include <stdint.h>
  29 #include <stddef.h>
  30 #include <mach/mach.h>
  31
  32 #if !TARGET_OS_DRIVERKIT && (BUILDING_LIBDYLD || BUILDING_DYLD)
  33   #include <CrashReporterClient.h>
  34 #else
  35   #define CRSetCrashLogMessage(x)
  36   #define CRSetCrashLogMessage2(x)
  37 #endif
  38
  39 #define VIS_HIDDEN __attribute__((visibility("hidden")))
  40
  41 namespace dyld3 {
  42
  43
  44 //
  45 // Similar to std::vector<> but storage is pre-allocated and cannot be re-allocated.
  46 // Storage is normally stack allocated.
  47 //
  48 // Use push_back() to add elements and range based for loops to iterate and [] to access by index.
  49 //
  50 template <typename T>
  51 class VIS_HIDDEN Array
  52 {
  53 public:
  54                     Array()                                 : _elements(nullptr), _allocCount(0), _usedCount(0) {}
  55                     Array(T* storage, uintptr_t allocCount, uintptr_t usedCount=0) : _elements(storage), _allocCount(allocCount), _usedCount(usedCount) {}
  56     void            setInitialStorage(T* storage, uintptr_t allocCount) { assert(_usedCount == 0); _elements=storage; _allocCount=allocCount; }
  57
  58     T&              operator[](size_t idx)       { assert(idx < _usedCount); return _elements[idx]; }
  59     const T&        operator[](size_t idx) const { assert(idx < _usedCount); return _elements[idx]; }
  60     T&              back()                       { assert(_usedCount > 0); return _elements[_usedCount-1]; }
  61     uintptr_t       count() const                { return _usedCount; }
  62     uintptr_t       maxCount() const             { return _allocCount; }
  63     uintptr_t       freeCount() const            { return _allocCount - _usedCount; }
  64     bool            empty() const                { return (_usedCount == 0); }
  65     uintptr_t       index(const T& element)      { return &element - _elements; }
  66     void            push_back(const T& t)        { assert(_usedCount < _allocCount); _elements[_usedCount++] = t; }
  67     void            default_constuct_back()      { assert(_usedCount < _allocCount); new (&_elements[_usedCount++])T(); }
  68     void            pop_back()                   { assert(_usedCount > 0); _usedCount--; }
  69     T*              begin()                      { return &_elements[0]; }
  70     T*              end()                        { return &_elements[_usedCount]; }
  71     const T*        begin() const                { return &_elements[0]; }
  72     const T*        end() const                  { return &_elements[_usedCount]; }
  73     const Array<T>  subArray(uintptr_t start, uintptr_t size) const { assert(start+size <= _usedCount);
  74                                                                       return Array<T>(&_elements[start], size, size); }
  75     bool            contains(const T& targ) const { for (const T& a : *this) { if ( a == targ ) return true; } return false; }
  76     void            remove(size_t idx)          { assert(idx < _usedCount); ::memmove(&_elements[idx], &_elements[idx+1], sizeof(T)*(_usedCount-idx-1)); }
  77
  78 protected:
  79     T*          _elements;
  80     uintptr_t   _allocCount;
  81     uintptr_t   _usedCount;
  82 };
  83
  84
  85 // If an Array<>.setInitialStorage() is used, the array may out live the stack space of the storage.
  86 // To allow cleanup to be done to array elements when the stack goes away, you can make a local
  87 // variable of ArrayFinalizer<>.
  88 template <typename T>
  89 class VIS_HIDDEN ArrayFinalizer
  90 {
  91 public:
  92     typedef void (^CleanUp)(T& element);
  93                     ArrayFinalizer(Array<T>& array, CleanUp handler) : _array(array), _handler(handler) { }
  94                     ~ArrayFinalizer() { for(T& element : _array) _handler(element); }
  95 private:
  96     Array<T>&   _array;
  97     CleanUp     _handler;
  98 };
  99
 100
 101
 102 //
 103 // Similar to Array<> but if the array overflows, it is re-allocated using vm_allocate().
 104 // When the variable goes out of scope, any vm_allocate()ed storage is released.
 105 // if MAXCOUNT is specified, then only one one vm_allocate() to that size is done.
 106 //
 107 template <typename T, uintptr_t MAXCOUNT=0xFFFFFFFF>
 108 class VIS_HIDDEN OverflowSafeArray : public Array<T>
 109 {
 110 public:
 111                     OverflowSafeArray() : Array<T>(nullptr, 0) {}
 112                     OverflowSafeArray(T* stackStorage, uintptr_t stackAllocCount) : Array<T>(stackStorage, stackAllocCount) {}
 113                     ~OverflowSafeArray();
 114
 115                     OverflowSafeArray(OverflowSafeArray&) = default;
 116                     OverflowSafeArray& operator=(OverflowSafeArray&& other);
 117
 118     void            push_back(const T& t)        { verifySpace(1); this->_elements[this->_usedCount++] = t; }
 119     void            default_constuct_back()      { verifySpace(1); new (&this->_elements[this->_usedCount++])T(); }
 120     void            clear() { this->_usedCount = 0; }
 121     void            reserve(uintptr_t n) { if (this->_allocCount < n) growTo(n); }
 122     void            resize(uintptr_t n) {
 123         if (n == this->_usedCount)
 124             return;
 125         if (n < this->_usedCount) {
 126             this->_usedCount = n;
 127             return;
 128         }
 129         reserve(n);
 130         this->_usedCount = n;
 131     }
 132
 133 protected:
 134     void            growTo(uintptr_t n);
 135     void            verifySpace(uintptr_t n)     { if (this->_usedCount+n > this->_allocCount) growTo(this->_usedCount + n); }
 136
 137 private:
 138     vm_address_t    _overflowBuffer         = 0;
 139     vm_size_t       _overflowBufferSize     = 0;
 140 };
 141
 142
 143 template <typename T, uintptr_t MAXCOUNT>
 144 inline void OverflowSafeArray<T,MAXCOUNT>::growTo(uintptr_t n)
 145 {
 146     vm_address_t    oldBuffer      = _overflowBuffer;
 147     vm_size_t       oldBufferSize  = _overflowBufferSize;
 148     if ( MAXCOUNT != 0xFFFFFFFF ) {
 149         assert(oldBufferSize == 0); // only re-alloc once
 150         // MAXCOUNT is specified, so immediately jump to that size
 151         _overflowBufferSize = round_page(std::max(MAXCOUNT, n) * sizeof(T));
 152     }
 153     else {
 154        // MAXCOUNT is not specified, keep doubling size
 155        _overflowBufferSize = round_page(std::max(this->_allocCount * 2, n) * sizeof(T));
 156     }
 157     kern_return_t kr = ::vm_allocate(mach_task_self(), &_overflowBuffer, _overflowBufferSize, VM_FLAGS_ANYWHERE);
 158     if (kr != KERN_SUCCESS) {
 159 #if BUILDING_LIBDYLD
 160         //FIXME We should figure out a way to do this in dyld
 161         char crashString[256];
 162         snprintf(crashString, 256, "OverflowSafeArray failed to allocate %lu bytes, vm_allocate returned: %d\n",
 163                 _overflowBufferSize, kr);
 164         CRSetCrashLogMessage(crashString);
 165 #endif
 166         assert(0);
 167     }
 168     ::memcpy((void*)_overflowBuffer, this->_elements, this->_usedCount*sizeof(T));
 169     this->_elements = (T*)_overflowBuffer;
 170     this->_allocCount = _overflowBufferSize / sizeof(T);
 171
 172     if ( oldBuffer != 0 )
 173         ::vm_deallocate(mach_task_self(), oldBuffer, oldBufferSize);
 174 }
 175
 176 template <typename T, uintptr_t MAXCOUNT>
 177 inline OverflowSafeArray<T,MAXCOUNT>::~OverflowSafeArray()
 178 {
 179     if ( _overflowBuffer != 0 )
 180         ::vm_deallocate(mach_task_self(), _overflowBuffer, _overflowBufferSize);
 181 }
 182
 183 template <typename T, uintptr_t MAXCOUNT>
 184 inline OverflowSafeArray<T,MAXCOUNT>& OverflowSafeArray<T,MAXCOUNT>::operator=(OverflowSafeArray<T,MAXCOUNT>&& other)
 185 {
 186     if (this == &other)
 187         return *this;
 188
 189     // Free our buffer if we have one
 190     if ( _overflowBuffer != 0 )
 191         ::vm_deallocate(mach_task_self(), _overflowBuffer, _overflowBufferSize);
 192
 193     // Now take the buffer from the other array
 194     this->_elements     = other._elements;
 195     this->_allocCount   = other._allocCount;
 196     this->_usedCount    = other._usedCount;
 197     _overflowBuffer     = other._overflowBuffer;
 198     _overflowBufferSize = other._overflowBufferSize;
 199
 200     // Now reset the other object so that it doesn't try to deallocate the memory later.
 201     other._elements             = nullptr;
 202     other._allocCount           = 0;
 203     other._usedCount            = 0;
 204     other._overflowBuffer       = 0;
 205     other._overflowBufferSize   = 0;
 206     return *this;
 207 }
 208
 209
 210
 211 #if BUILDING_LIBDYLD
 212 //
 213 // Similar to std::vector<> but storage is initially allocated in the object. But if it needs to
 214 // grow beyond, it will use malloc.  The QUANT template arg is the "quantum" size for allocations.
 215 // When the allocation needs to be grown, it is re-allocated at the required size rounded up to
 216 // the next quantum.
 217 //
 218 // Use push_back() to add elements and range based for loops to iterate and [] to access by index.
 219 //
 220 // Note: this should be a subclass of Array<T> but doing so disables the compiler from optimizing away static constructors
 221 //
 222 template <typename T, int QUANT=4, int INIT=1>
 223 class VIS_HIDDEN GrowableArray
 224 {
 225 public:
 226
 227     T&              operator[](size_t idx)       { assert(idx < _usedCount); return _elements[idx]; }
 228     const T&        operator[](size_t idx) const { assert(idx < _usedCount); return _elements[idx]; }
 229     T&              back()                       { assert(_usedCount > 0); return _elements[_usedCount-1]; }
 230     uintptr_t       count() const                { return _usedCount; }
 231     uintptr_t       maxCount() const             { return _allocCount; }
 232     bool            empty() const                { return (_usedCount == 0); }
 233     uintptr_t       index(const T& element)      { return &element - _elements; }
 234     void            push_back(const T& t)        { verifySpace(1); _elements[_usedCount++] = t; }
 235     void            append(const Array<T>& a);
 236     void            pop_back()                   { assert(_usedCount > 0); _usedCount--; }
 237     T*              begin()                      { return &_elements[0]; }
 238     T*              end()                        { return &_elements[_usedCount]; }
 239     const T*        begin() const                { return &_elements[0]; }
 240     const T*        end() const                  { return &_elements[_usedCount]; }
 241     const Array<T>  subArray(uintptr_t start, uintptr_t size) const { assert(start+size <= _usedCount);
 242                                                                       return Array<T>(&_elements[start], size, size); }
 243     const Array<T>& array() const                 { return *((Array<T>*)this); }
 244     bool            contains(const T& targ) const { for (const T& a : *this) { if ( a == targ ) return true; } return false; }
 245     void            erase(T& targ);
 246
 247 protected:
 248     void            growTo(uintptr_t n);
 249     void            verifySpace(uintptr_t n)     { if (this->_usedCount+n > this->_allocCount) growTo(this->_usedCount + n); }
 250
 251 private:
 252     T*              _elements               = _initialAlloc;
 253     uintptr_t       _allocCount             = INIT;
 254     uintptr_t       _usedCount              = 0;
 255     T               _initialAlloc[INIT]     = { };
 256 };
 257
 258
 259 template <typename T, int QUANT, int INIT>
 260 inline void GrowableArray<T,QUANT,INIT>::growTo(uintptr_t n)
 261 {
 262     uintptr_t newCount = (n + QUANT - 1) & (-QUANT);
 263     T* newArray = (T*)::malloc(sizeof(T)*newCount);
 264     T* oldArray = this->_elements;
 265     if ( this->_usedCount != 0 )
 266         ::memcpy(newArray, oldArray, sizeof(T)*this->_usedCount);
 267     this->_elements   = newArray;
 268     this->_allocCount = newCount;
 269     if ( oldArray != this->_initialAlloc )
 270         ::free(oldArray);
 271 }
 272
 273 template <typename T, int QUANT, int INIT>
 274 inline void GrowableArray<T,QUANT,INIT>::append(const Array<T>& a)
 275 {
 276     verifySpace(a.count());
 277     ::memcpy(&_elements[_usedCount], a.begin(), a.count()*sizeof(T));
 278     _usedCount += a.count();
 279 }
 280
 281 template <typename T, int QUANT, int INIT>
 282 inline void GrowableArray<T,QUANT,INIT>::erase(T& targ)
 283 {
 284     intptr_t index = &targ - _elements;
 285     assert(index >= 0);
 286     assert(index < (intptr_t)_usedCount);
 287     intptr_t moveCount = _usedCount-index-1;
 288     if ( moveCount > 0 )
 289         ::memcpy(&_elements[index], &_elements[index+1], moveCount*sizeof(T));
 290     _usedCount -= 1;
 291 }
 292
 293 #endif // BUILDING_LIBDYLD
 294
 295
 296
 297 //  STACK_ALLOC_ARRAY(foo, myarray, 10);
 298 //  myarray is of type Array<foo>
 299 #define STACK_ALLOC_ARRAY(_type, _name, _count)  \
 300     uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
 301     __block dyld3::Array<_type> _name((_type*)__##_name##_array_alloc, _count);
 302
 303
 304 //  STACK_ALLOC_OVERFLOW_SAFE_ARRAY(foo, myarray, 10);
 305 //  myarray is of type OverflowSafeArray<foo>
 306 #define STACK_ALLOC_OVERFLOW_SAFE_ARRAY(_type, _name, _count)  \
 307     uintptr_t __##_name##_array_alloc[1 + ((sizeof(_type)*(_count))/sizeof(uintptr_t))]; \
 308     __block dyld3::OverflowSafeArray<_type> _name((_type*)__##_name##_array_alloc, _count);
 309
 310
 311 //  work around compiler bug where:
 312 //       __block type name[count];
 313 //  is not accessible in a block
 314 #define BLOCK_ACCCESSIBLE_ARRAY(_type, _name, _count)  \
 315     _type __##_name##_array_alloc[_count]; \
 316     _type* _name = __##_name##_array_alloc;
 317
 318
 319 } // namespace dyld3
 320
 321 #endif /* Array_h */