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