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