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