1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- 2 * vim: set ts=8 sts=2 et sw=2 tw=80: 3 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef jit_shared_IonAssemblerBuffer_h 8 #define jit_shared_IonAssemblerBuffer_h 9 10 #include "mozilla/Assertions.h" 11 #include "mozilla/MathAlgorithms.h" 12 13 #include <algorithm> 14 15 #include "jit/shared/Assembler-shared.h" 16 17 namespace js { 18 namespace jit { 19 20 // The offset into a buffer, in bytes. 21 class BufferOffset { 22 int offset; 23 24 public: 25 friend BufferOffset nextOffset(); 26 BufferOffset()27 BufferOffset() : offset(INT_MIN) {} 28 BufferOffset(int offset_)29 explicit BufferOffset(int offset_) : offset(offset_) { 30 MOZ_ASSERT(offset >= 0); 31 } 32 BufferOffset(Label * l)33 explicit BufferOffset(Label* l) : offset(l->offset()) { 34 MOZ_ASSERT(offset >= 0); 35 } 36 getOffset()37 int getOffset() const { return offset; } assigned()38 bool assigned() const { return offset != INT_MIN; } 39 40 // A BOffImm is a Branch Offset Immediate. It is an architecture-specific 41 // structure that holds the immediate for a pc relative branch. diffB takes 42 // the label for the destination of the branch, and encodes the immediate 43 // for the branch. This will need to be fixed up later, since A pool may be 44 // inserted between the branch and its destination. 45 template <class BOffImm> diffB(BufferOffset other)46 BOffImm diffB(BufferOffset other) const { 47 if (!BOffImm::IsInRange(offset - other.offset)) { 48 return BOffImm(); 49 } 50 return BOffImm(offset - other.offset); 51 } 52 53 template <class BOffImm> diffB(Label * other)54 BOffImm diffB(Label* other) const { 55 MOZ_ASSERT(other->bound()); 56 if (!BOffImm::IsInRange(offset - other->offset())) { 57 return BOffImm(); 58 } 59 return BOffImm(offset - other->offset()); 60 } 61 }; 62 63 inline bool operator<(BufferOffset a, BufferOffset b) { 64 return a.getOffset() < b.getOffset(); 65 } 66 67 inline bool operator>(BufferOffset a, BufferOffset b) { 68 return a.getOffset() > b.getOffset(); 69 } 70 71 inline bool operator<=(BufferOffset a, BufferOffset b) { 72 return a.getOffset() <= b.getOffset(); 73 } 74 75 inline bool operator>=(BufferOffset a, BufferOffset b) { 76 return a.getOffset() >= b.getOffset(); 77 } 78 79 inline bool operator==(BufferOffset a, BufferOffset b) { 80 return a.getOffset() == b.getOffset(); 81 } 82 83 inline bool operator!=(BufferOffset a, BufferOffset b) { 84 return a.getOffset() != b.getOffset(); 85 } 86 87 template <int SliceSize> 88 class BufferSlice { 89 protected: 90 BufferSlice<SliceSize>* prev_; 91 BufferSlice<SliceSize>* next_; 92 93 size_t bytelength_; 94 95 public: 96 mozilla::Array<uint8_t, SliceSize> instructions; 97 98 public: BufferSlice()99 explicit BufferSlice() : prev_(nullptr), next_(nullptr), bytelength_(0) {} 100 length()101 size_t length() const { return bytelength_; } Capacity()102 static inline size_t Capacity() { return SliceSize; } 103 getNext()104 BufferSlice* getNext() const { return next_; } getPrev()105 BufferSlice* getPrev() const { return prev_; } 106 setNext(BufferSlice<SliceSize> * next)107 void setNext(BufferSlice<SliceSize>* next) { 108 MOZ_ASSERT(next_ == nullptr); 109 MOZ_ASSERT(next->prev_ == nullptr); 110 next_ = next; 111 next->prev_ = this; 112 } 113 putBytes(size_t numBytes,const void * source)114 void putBytes(size_t numBytes, const void* source) { 115 MOZ_ASSERT(bytelength_ + numBytes <= SliceSize); 116 if (source) { 117 memcpy(&instructions[length()], source, numBytes); 118 } 119 bytelength_ += numBytes; 120 } 121 122 MOZ_ALWAYS_INLINE putU32Aligned(uint32_t value)123 void putU32Aligned(uint32_t value) { 124 MOZ_ASSERT(bytelength_ + 4 <= SliceSize); 125 MOZ_ASSERT((bytelength_ & 3) == 0); 126 MOZ_ASSERT((uintptr_t(&instructions[0]) & 3) == 0); 127 *reinterpret_cast<uint32_t*>(&instructions[bytelength_]) = value; 128 bytelength_ += 4; 129 } 130 }; 131 132 template <int SliceSize, class Inst> 133 class AssemblerBuffer { 134 protected: 135 typedef BufferSlice<SliceSize> Slice; 136 137 // Doubly-linked list of BufferSlices, with the most recent in tail position. 138 Slice* head; 139 Slice* tail; 140 141 bool m_oom; 142 143 // How many bytes has been committed to the buffer thus far. 144 // Does not include tail. 145 uint32_t bufferSize; 146 147 // How many bytes can be in the buffer. Normally this is 148 // MaxCodeBytesPerBuffer, but for pasteup buffers where we handle far jumps 149 // explicitly it can be larger. 150 uint32_t maxSize; 151 152 // Finger for speeding up accesses. 153 Slice* finger; 154 int finger_offset; 155 156 LifoAlloc lifoAlloc_; 157 158 public: AssemblerBuffer()159 explicit AssemblerBuffer() 160 : head(nullptr), 161 tail(nullptr), 162 m_oom(false), 163 bufferSize(0), 164 maxSize(MaxCodeBytesPerBuffer), 165 finger(nullptr), 166 finger_offset(0), 167 lifoAlloc_(8192) {} 168 169 public: isAligned(size_t alignment)170 bool isAligned(size_t alignment) const { 171 MOZ_ASSERT(mozilla::IsPowerOfTwo(alignment)); 172 return !(size() & (alignment - 1)); 173 } 174 setUnlimited()175 void setUnlimited() { maxSize = MaxCodeBytesPerProcess; } 176 177 private: newSlice(LifoAlloc & a)178 Slice* newSlice(LifoAlloc& a) { 179 if (size() > maxSize - sizeof(Slice)) { 180 fail_oom(); 181 return nullptr; 182 } 183 Slice* tmp = static_cast<Slice*>(a.alloc(sizeof(Slice))); 184 if (!tmp) { 185 fail_oom(); 186 return nullptr; 187 } 188 return new (tmp) Slice; 189 } 190 191 public: ensureSpace(size_t size)192 bool ensureSpace(size_t size) { 193 // Space can exist in the most recent Slice. 194 if (tail && tail->length() + size <= tail->Capacity()) { 195 // Simulate allocation failure even when we don't need a new slice. 196 if (js::oom::ShouldFailWithOOM()) { 197 return fail_oom(); 198 } 199 200 return true; 201 } 202 203 // Otherwise, a new Slice must be added. 204 Slice* slice = newSlice(lifoAlloc_); 205 if (slice == nullptr) { 206 return fail_oom(); 207 } 208 209 // If this is the first Slice in the buffer, add to head position. 210 if (!head) { 211 head = slice; 212 finger = slice; 213 finger_offset = 0; 214 } 215 216 // Finish the last Slice and add the new Slice to the linked list. 217 if (tail) { 218 bufferSize += tail->length(); 219 tail->setNext(slice); 220 } 221 tail = slice; 222 223 return true; 224 } 225 putByte(uint8_t value)226 BufferOffset putByte(uint8_t value) { 227 return putBytes(sizeof(value), &value); 228 } 229 putShort(uint16_t value)230 BufferOffset putShort(uint16_t value) { 231 return putBytes(sizeof(value), &value); 232 } 233 putInt(uint32_t value)234 BufferOffset putInt(uint32_t value) { 235 return putBytes(sizeof(value), &value); 236 } 237 238 MOZ_ALWAYS_INLINE putU32Aligned(uint32_t value)239 BufferOffset putU32Aligned(uint32_t value) { 240 if (!ensureSpace(sizeof(value))) { 241 return BufferOffset(); 242 } 243 244 BufferOffset ret = nextOffset(); 245 tail->putU32Aligned(value); 246 return ret; 247 } 248 249 // Add numBytes bytes to this buffer. 250 // The data must fit in a single slice. putBytes(size_t numBytes,const void * inst)251 BufferOffset putBytes(size_t numBytes, const void* inst) { 252 if (!ensureSpace(numBytes)) { 253 return BufferOffset(); 254 } 255 256 BufferOffset ret = nextOffset(); 257 tail->putBytes(numBytes, inst); 258 return ret; 259 } 260 261 // Add a potentially large amount of data to this buffer. 262 // The data may be distrubuted across multiple slices. 263 // Return the buffer offset of the first added byte. putBytesLarge(size_t numBytes,const void * data)264 BufferOffset putBytesLarge(size_t numBytes, const void* data) { 265 BufferOffset ret = nextOffset(); 266 while (numBytes > 0) { 267 if (!ensureSpace(1)) { 268 return BufferOffset(); 269 } 270 size_t avail = tail->Capacity() - tail->length(); 271 size_t xfer = numBytes < avail ? numBytes : avail; 272 MOZ_ASSERT(xfer > 0, "ensureSpace should have allocated a slice"); 273 tail->putBytes(xfer, data); 274 data = (const uint8_t*)data + xfer; 275 numBytes -= xfer; 276 } 277 return ret; 278 } 279 size()280 unsigned int size() const { 281 if (tail) { 282 return bufferSize + tail->length(); 283 } 284 return bufferSize; 285 } nextOffset()286 BufferOffset nextOffset() const { return BufferOffset(size()); } 287 oom()288 bool oom() const { return m_oom; } 289 fail_oom()290 bool fail_oom() { 291 m_oom = true; 292 #ifdef DEBUG 293 JitContext* context = MaybeGetJitContext(); 294 if (context) { 295 context->setOOM(); 296 } 297 #endif 298 return false; 299 } 300 301 private: update_finger(Slice * finger_,int fingerOffset_)302 void update_finger(Slice* finger_, int fingerOffset_) { 303 finger = finger_; 304 finger_offset = fingerOffset_; 305 } 306 307 static const unsigned SliceDistanceRequiringFingerUpdate = 3; 308 309 Inst* getInstForwards(BufferOffset off, Slice* start, int startOffset, 310 bool updateFinger = false) { 311 const int offset = off.getOffset(); 312 313 int cursor = startOffset; 314 unsigned slicesSkipped = 0; 315 316 MOZ_ASSERT(offset >= cursor); 317 318 for (Slice* slice = start; slice != nullptr; slice = slice->getNext()) { 319 const int slicelen = slice->length(); 320 321 // Is the offset within the bounds of this slice? 322 if (offset < cursor + slicelen) { 323 if (updateFinger || 324 slicesSkipped >= SliceDistanceRequiringFingerUpdate) { 325 update_finger(slice, cursor); 326 } 327 328 MOZ_ASSERT(offset - cursor < (int)slice->length()); 329 return (Inst*)&slice->instructions[offset - cursor]; 330 } 331 332 cursor += slicelen; 333 slicesSkipped++; 334 } 335 336 MOZ_CRASH("Invalid instruction cursor."); 337 } 338 339 Inst* getInstBackwards(BufferOffset off, Slice* start, int startOffset, 340 bool updateFinger = false) { 341 const int offset = off.getOffset(); 342 343 int cursor = startOffset; // First (lowest) offset in the start Slice. 344 unsigned slicesSkipped = 0; 345 346 MOZ_ASSERT(offset < int(cursor + start->length())); 347 348 for (Slice* slice = start; slice != nullptr;) { 349 // Is the offset within the bounds of this slice? 350 if (offset >= cursor) { 351 if (updateFinger || 352 slicesSkipped >= SliceDistanceRequiringFingerUpdate) { 353 update_finger(slice, cursor); 354 } 355 356 MOZ_ASSERT(offset - cursor < (int)slice->length()); 357 return (Inst*)&slice->instructions[offset - cursor]; 358 } 359 360 // Move the cursor to the start of the previous slice. 361 Slice* prev = slice->getPrev(); 362 cursor -= prev->length(); 363 364 slice = prev; 365 slicesSkipped++; 366 } 367 368 MOZ_CRASH("Invalid instruction cursor."); 369 } 370 371 public: getInstOrNull(BufferOffset off)372 Inst* getInstOrNull(BufferOffset off) { 373 if (!off.assigned()) { 374 return nullptr; 375 } 376 return getInst(off); 377 } 378 379 // Get a pointer to the instruction at offset |off| which must be within the 380 // bounds of the buffer. Use |getInstOrNull()| if |off| may be unassigned. getInst(BufferOffset off)381 Inst* getInst(BufferOffset off) { 382 const int offset = off.getOffset(); 383 // This function is hot, do not make the next line a RELEASE_ASSERT. 384 MOZ_ASSERT(off.assigned() && offset >= 0 && unsigned(offset) < size()); 385 386 // Is the instruction in the last slice? 387 if (offset >= int(bufferSize)) { 388 return (Inst*)&tail->instructions[offset - bufferSize]; 389 } 390 391 // How close is this offset to the previous one we looked up? 392 // If it is sufficiently far from the start and end of the buffer, 393 // use the finger to start midway through the list. 394 int finger_dist = abs(offset - finger_offset); 395 if (finger_dist < std::min(offset, int(bufferSize - offset))) { 396 if (finger_offset < offset) { 397 return getInstForwards(off, finger, finger_offset, true); 398 } 399 return getInstBackwards(off, finger, finger_offset, true); 400 } 401 402 // Is the instruction closer to the start or to the end? 403 if (offset < int(bufferSize - offset)) { 404 return getInstForwards(off, head, 0); 405 } 406 407 // The last slice was already checked above, so start at the 408 // second-to-last. 409 Slice* prev = tail->getPrev(); 410 return getInstBackwards(off, prev, bufferSize - prev->length()); 411 } 412 413 typedef AssemblerBuffer<SliceSize, Inst> ThisClass; 414 415 class AssemblerBufferInstIterator { 416 BufferOffset bo_; 417 ThisClass* buffer_; 418 419 public: AssemblerBufferInstIterator(BufferOffset bo,ThisClass * buffer)420 explicit AssemblerBufferInstIterator(BufferOffset bo, ThisClass* buffer) 421 : bo_(bo), buffer_(buffer) {} advance(int offset)422 void advance(int offset) { bo_ = BufferOffset(bo_.getOffset() + offset); } next()423 Inst* next() { 424 advance(cur()->size()); 425 return cur(); 426 } peek()427 Inst* peek() { 428 return buffer_->getInst(BufferOffset(bo_.getOffset() + cur()->size())); 429 } cur()430 Inst* cur() const { return buffer_->getInst(bo_); } 431 }; 432 }; 433 434 } // namespace jit 435 } // namespace js 436 437 #endif // jit_shared_IonAssemblerBuffer_h 438