1/* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 14 * its contributors may be used to endorse or promote products derived 15 * from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 20 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 23 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#ifndef CompactJITCodeMap_h 30#define CompactJITCodeMap_h 31 32#include <wtf/Assertions.h> 33#include <wtf/FastAllocBase.h> 34#include <wtf/FastMalloc.h> 35#include <wtf/OwnPtr.h> 36#include <wtf/PassOwnPtr.h> 37#include <wtf/Vector.h> 38 39namespace JSC { 40 41// Gives you a compressed map between between bytecode indices and machine code 42// entry points. The compression simply tries to use either 1, 2, or 4 bytes for 43// any given offset. The largest offset that can be stored is 2^30. 44 45// Example use: 46// 47// CompactJITCodeMap::Encoder encoder(map); 48// encoder.append(a, b); 49// encoder.append(c, d); // preconditions: c >= a, d >= b 50// OwnPtr<CompactJITCodeMap> map = encoder.finish(); 51// 52// At some later time: 53// 54// Vector<BytecodeAndMachineOffset> decoded; 55// map->decode(decoded); 56 57struct BytecodeAndMachineOffset { 58 BytecodeAndMachineOffset() { } 59 60 BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset) 61 : m_bytecodeIndex(bytecodeIndex) 62 , m_machineCodeOffset(machineCodeOffset) 63 { 64 } 65 66 unsigned m_bytecodeIndex; 67 unsigned m_machineCodeOffset; 68 69 static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping) 70 { 71 return mapping->m_bytecodeIndex; 72 } 73 74 static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping) 75 { 76 return mapping->m_machineCodeOffset; 77 } 78}; 79 80class CompactJITCodeMap { 81 WTF_MAKE_FAST_ALLOCATED; 82public: 83 ~CompactJITCodeMap() 84 { 85 if (m_buffer) 86 fastFree(m_buffer); 87 } 88 89 unsigned numberOfEntries() const 90 { 91 return m_numberOfEntries; 92 } 93 94 void decode(Vector<BytecodeAndMachineOffset>& result) const; 95 96private: 97 CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries) 98 : m_buffer(buffer) 99#if !ASSERT_DISABLED 100 , m_size(size) 101#endif 102 , m_numberOfEntries(numberOfEntries) 103 { 104 UNUSED_PARAM(size); 105 } 106 107 uint8_t at(unsigned index) const 108 { 109 ASSERT(index < m_size); 110 return m_buffer[index]; 111 } 112 113 unsigned decodeNumber(unsigned& index) const 114 { 115 uint8_t headValue = at(index++); 116 if (!(headValue & 128)) 117 return headValue; 118 if (!(headValue & 64)) 119 return (static_cast<unsigned>(headValue & ~128) << 8) | at(index++); 120 unsigned second = at(index++); 121 unsigned third = at(index++); 122 unsigned fourth = at(index++); 123 return (static_cast<unsigned>(headValue & ~(128 + 64)) << 24) | (second << 16) | (third << 8) | fourth; 124 } 125 126 uint8_t* m_buffer; 127#if !ASSERT_DISABLED 128 unsigned m_size; 129#endif 130 unsigned m_numberOfEntries; 131 132public: 133 class Encoder { 134 WTF_MAKE_NONCOPYABLE(Encoder); 135 public: 136 Encoder(); 137 ~Encoder(); 138 139 void ensureCapacityFor(unsigned numberOfEntriesToAdd); 140 void append(unsigned bytecodeIndex, unsigned machineCodeOffset); 141 PassOwnPtr<CompactJITCodeMap> finish(); 142 143 private: 144 void appendByte(uint8_t value); 145 void encodeNumber(uint32_t value); 146 147 uint8_t* m_buffer; 148 unsigned m_size; 149 unsigned m_capacity; 150 unsigned m_numberOfEntries; 151 152 unsigned m_previousBytecodeIndex; 153 unsigned m_previousMachineCodeOffset; 154 }; 155 156 class Decoder { 157 WTF_MAKE_NONCOPYABLE(Decoder); 158 public: 159 Decoder(const CompactJITCodeMap*); 160 161 unsigned numberOfEntriesRemaining() const; 162 void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset); 163 164 private: 165 const CompactJITCodeMap* m_jitCodeMap; 166 unsigned m_previousBytecodeIndex; 167 unsigned m_previousMachineCodeOffset; 168 unsigned m_numberOfEntriesRemaining; 169 unsigned m_bufferIndex; 170 }; 171 172private: 173 friend class Encoder; 174 friend class Decoder; 175}; 176 177inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const 178{ 179 Decoder decoder(this); 180 result.resize(decoder.numberOfEntriesRemaining()); 181 for (unsigned i = 0; i < result.size(); ++i) 182 decoder.read(result[i].m_bytecodeIndex, result[i].m_machineCodeOffset); 183 184 ASSERT(!decoder.numberOfEntriesRemaining()); 185} 186 187inline CompactJITCodeMap::Encoder::Encoder() 188 : m_buffer(0) 189 , m_size(0) 190 , m_capacity(0) 191 , m_numberOfEntries(0) 192 , m_previousBytecodeIndex(0) 193 , m_previousMachineCodeOffset(0) 194{ 195} 196 197inline CompactJITCodeMap::Encoder::~Encoder() 198{ 199 if (m_buffer) 200 fastFree(m_buffer); 201} 202 203inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset) 204{ 205 ASSERT(bytecodeIndex >= m_previousBytecodeIndex); 206 ASSERT(machineCodeOffset >= m_previousMachineCodeOffset); 207 ensureCapacityFor(1); 208 encodeNumber(bytecodeIndex - m_previousBytecodeIndex); 209 encodeNumber(machineCodeOffset - m_previousMachineCodeOffset); 210 m_previousBytecodeIndex = bytecodeIndex; 211 m_previousMachineCodeOffset = machineCodeOffset; 212 m_numberOfEntries++; 213} 214 215inline PassOwnPtr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish() 216{ 217 m_capacity = m_size; 218 m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity)); 219 OwnPtr<CompactJITCodeMap> result = adoptPtr(new CompactJITCodeMap(m_buffer, m_size, m_numberOfEntries)); 220 m_buffer = 0; 221 m_size = 0; 222 m_capacity = 0; 223 m_numberOfEntries = 0; 224 m_previousBytecodeIndex = 0; 225 m_previousMachineCodeOffset = 0; 226 return result.release(); 227} 228 229inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value) 230{ 231 ASSERT(m_size + 1 <= m_capacity); 232 m_buffer[m_size++] = value; 233} 234 235inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value) 236{ 237 ASSERT(m_size + 4 <= m_capacity); 238 ASSERT(value < (1 << 30)); 239 if (value <= 127) { 240 uint8_t headValue = static_cast<uint8_t>(value); 241 ASSERT(!(headValue & 128)); 242 appendByte(headValue); 243 } else if (value <= 16383) { 244 uint8_t headValue = static_cast<uint8_t>(value >> 8); 245 ASSERT(!(headValue & 128)); 246 ASSERT(!(headValue & 64)); 247 appendByte(headValue | 128); 248 appendByte(static_cast<uint8_t>(value)); 249 } else { 250 uint8_t headValue = static_cast<uint8_t>(value >> 24); 251 ASSERT(!(headValue & 128)); 252 ASSERT(!(headValue & 64)); 253 appendByte(headValue | 128 | 64); 254 appendByte(static_cast<uint8_t>(value >> 16)); 255 appendByte(static_cast<uint8_t>(value >> 8)); 256 appendByte(static_cast<uint8_t>(value)); 257 } 258} 259 260inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd) 261{ 262 unsigned capacityNeeded = m_size + numberOfEntriesToAdd * 2 * 4; 263 if (capacityNeeded > m_capacity) { 264 m_capacity = capacityNeeded * 2; 265 m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity)); 266 } 267} 268 269inline CompactJITCodeMap::Decoder::Decoder(const CompactJITCodeMap* jitCodeMap) 270 : m_jitCodeMap(jitCodeMap) 271 , m_previousBytecodeIndex(0) 272 , m_previousMachineCodeOffset(0) 273 , m_numberOfEntriesRemaining(jitCodeMap->m_numberOfEntries) 274 , m_bufferIndex(0) 275{ 276} 277 278inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const 279{ 280 ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size); 281 return m_numberOfEntriesRemaining; 282} 283 284inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset) 285{ 286 ASSERT(numberOfEntriesRemaining()); 287 288 m_previousBytecodeIndex += m_jitCodeMap->decodeNumber(m_bufferIndex); 289 m_previousMachineCodeOffset += m_jitCodeMap->decodeNumber(m_bufferIndex); 290 bytecodeIndex = m_previousBytecodeIndex; 291 machineCodeOffset = m_previousMachineCodeOffset; 292 m_numberOfEntriesRemaining--; 293} 294 295} // namespace JSC 296 297#endif // CompactJITCodeMap_h 298