Source code: Allocator/CodeAllocator.java
1 // CodeAllocator.java, created Mon Feb 5 23:23:19 2001 by joewhaley
2 // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3 // Licensed under the terms of the GNU LGPL; see COPYING for details.
4 package Allocator;
5
6 import java.util.Iterator;
7 import java.util.List;
8 import java.util.SortedMap;
9 import java.util.TreeMap;
10
11 import Bootstrap.PrimordialClassLoader;
12 import Clazz.jq_BytecodeMap;
13 import Clazz.jq_Class;
14 import Clazz.jq_CompiledCode;
15 import Clazz.jq_InstanceField;
16 import Clazz.jq_Method;
17 import Clazz.jq_StaticField;
18 import Clazz.jq_TryCatch;
19 import Memory.Address;
20 import Memory.CodeAddress;
21 import Run_Time.ExceptionDeliverer;
22
23 /**
24 * This class provides the abstract interface for code allocators. A code
25 * allocator handles the allocation and management of code buffers.
26 *
27 * It also provides static methods for keeping track of the compiled methods and
28 * their address ranges.
29 *
30 * It also includes an inner class that provides the interface for code buffers.
31 *
32 * @author John Whaley <jwhaley@alum.mit.edu>
33 * @version $Id: CodeAllocator.java,v 1.19 2003/05/12 10:04:52 joewhaley Exp $
34 */
35 public abstract class CodeAllocator {
36
37 /** Trace flag. */
38 public static /*final*/ boolean TRACE = false;
39
40 /**
41 * Initialize this code allocator. This method is always called before the
42 * code allocator is actually used.
43 */
44 public abstract void init();
45
46 /**
47 * Allocate a code buffer of the given estimated size, such that the given
48 * offset will have the given alignment.
49 * It is legal for code to exceed the estimated size, but the cost may be
50 * high (i.e. it may require recopying of the buffer.)
51 *
52 * @param estimatedSize estimated size, in bytes, of desired code buffer
53 * @param offset desired offset to align to
54 * @param alignment desired alignment, or 0 if don't care
55 * @return the new code buffer
56 */
57 public abstract x86CodeBuffer getCodeBuffer(int estimatedSize,
58 int offset,
59 int alignment);
60
61 /**
62 * Patch the given address to refer to the other given address, in
63 * absolute terms. This is used to patch heap address references in the
64 * code, and code references in the heap.
65 *
66 * @param addr1 address to patch
67 * @param addr2 address to patch to
68 */
69 public abstract void patchAbsolute(Address addr1,
70 Address addr2);
71
72 /**
73 * Patch the given code address to refer to the given code address, in
74 * relative terms. This is used to patch branch targets in the code.
75 *
76 * @param code code address to patch
77 * @param target code address to patch to
78 */
79 public abstract void patchRelativeOffset(CodeAddress code,
80 CodeAddress target);
81
82 /**
83 * This class provides the interface for x86 code buffers.
84 * These code buffers are used to store generated x86 code.
85 * After the code is generated, use the allocateCodeBlock method to obtain
86 * a jq_CompiledCode object.
87 */
88 public abstract static class x86CodeBuffer {
89
90 /**
91 * Returns the current offset in this code buffer.
92 * @return current offset
93 */
94 public abstract int getCurrentOffset();
95
96 /**
97 * Returns the current address in this code buffer.
98 * @return current address
99 */
100 public abstract CodeAddress getStartAddress();
101
102 /**
103 * Returns the current address in this code buffer.
104 * @return current address
105 */
106 public abstract CodeAddress getCurrentAddress();
107
108 /**
109 * Sets the current address as the entrypoint to this code buffer.
110 */
111 public abstract void setEntrypoint();
112
113 /**
114 * Adds one byte to the end of this code buffer. Offset/address
115 * increase by 1.
116 * @param i the byte to add
117 */
118 public abstract void add1(byte i);
119
120 /**
121 * Adds two bytes (little-endian) to the end of this code buffer.
122 * Offset/address increase by 2.
123 * @param i the little-endian value to add
124 */
125 public abstract void add2_endian(int i);
126
127 /**
128 * Adds two bytes (big-endian) to the end of this code buffer.
129 * Offset/address increase by 2.
130 * @param i the big-endian value to add
131 */
132 public abstract void add2(int i);
133
134 /**
135 * Adds three bytes (big-endian) to the end of this code buffer.
136 * Offset/address increase by 3.
137 * @param i the big-endian value to add
138 */
139 public abstract void add3(int i);
140
141 /**
142 * Adds four bytes (little-endian) to the end of this code buffer.
143 * Offset/address increase by 4.
144 * @param i the little-endian value to add
145 */
146 public abstract void add4_endian(int i);
147
148 /**
149 * Gets the byte at the given offset in this code buffer.
150 *
151 * @param k offset of byte to return
152 * @return byte at given offset
153 */
154 public abstract byte get1(int k);
155
156 /**
157 * Gets the (little-endian) 4 bytes at the given offset in this
158 * code buffer.
159 *
160 * @param k offset of little-endian 4 bytes to return
161 * @return little-endian 4 bytes at given offset
162 */
163 public abstract int get4_endian(int k);
164
165 /**
166 * Sets the byte at the given offset to the given value.
167 * @param k offset of byte to set
168 * @param instr value to set it to
169 */
170 public abstract void put1(int k, byte instr);
171
172 /**
173 * Sets the 4 bytes at the given offset to the given (little-endian)
174 * value.
175 * @param k offset of 4 bytes to set
176 * @param instr little-endian value to set it to
177 */
178 public abstract void put4_endian(int k, int instr);
179
180 public abstract void skip(int nbytes);
181
182 /**
183 * Uses the code in this buffer, along with the arguments, to create
184 * a jq_CompiledCode object. Call this method after you are done
185 * generating code, and actually want to use it.
186 *
187 * @param m Java method of this code block, or null if none
188 * @param ex exception handler table, or null if none
189 * @param bcm bytecode map, or null if none
190 * @param x exception deliverer to use for this code, or null if none
191 * @param stackframesize size of stack frame in bytes
192 * @param codeRelocs list of code relocations for this code buffer, or
193 * null if none
194 * @param dataRelocs list of data relocations for this code buffer, or
195 * null if none
196 * @return a new jq_CompiledCode object for the code
197 */
198 public abstract jq_CompiledCode allocateCodeBlock(jq_Method m,
199 jq_TryCatch[] ex,
200 jq_BytecodeMap bcm,
201 ExceptionDeliverer x,
202 int stackframesize,
203 List codeRelocs,
204 List dataRelocs);
205 }
206
207 /** Map of compiled methods, sorted by address. */
208 private static final SortedMap compiledMethods;
209
210 /**
211 * Address range of compiled code. Code outside of this range cannot be
212 * generated by us.
213 */
214 private static CodeAddress lowAddress, highAddress;
215 static {
216 compiledMethods = new TreeMap();
217 }
218
219 public static void initializeCompiledMethodMap() {
220 lowAddress = (CodeAddress) CodeAddress.getNull().offset(0x7FFFFFFF);
221 highAddress = CodeAddress.getNull();
222 jq_CompiledCode cc = new jq_CompiledCode(null, highAddress, 0, highAddress,
223 null, null, null, 0, null, null);
224 compiledMethods.put(cc, cc);
225 }
226
227 /**
228 * Register the given compiled code, so lookups by address will return
229 * this code.
230 *
231 * @param cc compiled code to register
232 */
233 public static void registerCode(jq_CompiledCode cc) {
234 if (TRACE) System.out.println("Registering code: " + cc);
235 if (lowAddress == null || cc.getStart().difference(lowAddress) < 0)
236 lowAddress = cc.getStart();
237 if (highAddress == null || highAddress.difference(cc.getStart().offset(cc.getLength())) < 0)
238 highAddress = (CodeAddress)cc.getStart().offset(cc.getLength());
239 compiledMethods.put(cc, cc);
240 }
241
242 /**
243 * Return the compiled code which contains the given code address.
244 * Returns null if there is no registered code that contains the
245 * given address.
246 *
247 * @param ip code address to check
248 * @return compiled code containing given address, or null
249 */
250 public static jq_CompiledCode getCodeContaining(CodeAddress ip) {
251 InstructionPointer iptr = new InstructionPointer(ip);
252 return (jq_CompiledCode) compiledMethods.get(iptr);
253 }
254
255 /**
256 * Returns the lowest address of any registered code.
257 * @return lowest address of any registered code.
258 */
259 public static CodeAddress getLowAddress() { return lowAddress; }
260 /**
261 * Returns the highest address of any registered code.
262 * @return highest address of any registered code.
263 */
264 public static CodeAddress getHighAddress() { return highAddress; }
265
266 /**
267 * Returns an iterator of the registered jq_CompiledCode objects, in
268 * address order.
269 * @return iterator of jq_CompiledCode objects
270 */
271 public static Iterator/*<jq_CompiledCode>*/ getCompiledMethods() {
272 Iterator i = compiledMethods.keySet().iterator();
273 i.next(); // skip bogus compiled code
274 return i;
275 }
276
277 /**
278 * Returns the number of registered jq_CompiledCode objects.
279 * @return number of registered jq_CompiledCode objects
280 */
281 public static int getNumberOfCompiledMethods() {
282 return compiledMethods.keySet().size() - 1; // skip bogus compiled code
283 }
284
285 /**
286 * An object of this class represents a code address.
287 * It can be compared with a jq_CompiledCode object with compareTo and
288 * equals. They are equal if the InstructionPointer points within the
289 * range of the compiled code; the InstructionPointer is less if it is
290 * before the start address of the compiled code; the InstructionPointer
291 * is less if it is after the end address of the compiled code.
292 */
293 public static class InstructionPointer implements Comparable {
294
295 /** The (actual) address. */
296 private final CodeAddress ip;
297
298 /**
299 * Create a new instruction pointer.
300 * @param ip instruction pointer value
301 */
302 public InstructionPointer(CodeAddress ip) { this.ip = ip; }
303
304 /**
305 * Extract the address of this instruction pointer.
306 * @return address of this instruction pointer
307 */
308 public CodeAddress getIP() { return ip; }
309
310 /**
311 * Compare this instruction pointer to a compiled code object.
312 * @param that compiled code to compare against
313 * @return -1 if this ip comes before the given code, 0 if it is
314 * inside the given code, 1 if it is after the given code
315 */
316 public int compareTo(jq_CompiledCode that) {
317 CodeAddress ip = this.getIP();
318 CodeAddress start = that.getStart();
319 if (start.difference(ip) >= 0) return -1;
320 if (start.offset(that.getLength()).difference(ip) < 0) return 1;
321 return 0;
322 }
323
324 /**
325 * Compare this instruction pointer to another instruction pointer.
326 * @param that instruction pointer to compare against
327 * @return -1 if this ip is before the given ip, 0 if it is equal
328 * to the given ip, 1 if it is after the given ip
329 */
330 public int compareTo(InstructionPointer that) {
331 if (this.ip.difference(that.ip) < 0) return -1;
332 if (this.ip.difference(that.ip) > 0) return 1;
333 return 0;
334 }
335
336 /**
337 * Compares this instruction pointer to the given object
338 * (InstructionPointer or jq_CompiledCode)
339 * @param that object to compare to
340 * @return -1 if this is less than, 0 if this is equal, 1 if this
341 * is greater than
342 */
343 public int compareTo(java.lang.Object that) {
344 if (that instanceof jq_CompiledCode)
345 return compareTo((jq_CompiledCode) that);
346 else
347 return compareTo((InstructionPointer) that);
348 }
349
350 /**
351 * Returns true if this instruction pointer refers to a location
352 * within the given compiled code, false otherwise.
353 * @param that compiled code to compare to
354 * @return true if the instruction pointer is within, false otherwise
355 */
356 public boolean equals(jq_CompiledCode that) {
357 CodeAddress ip = this.getIP();
358 CodeAddress start = that.getStart();
359 if (ip.difference(start) < 0) return false;
360 if (ip.difference(start.offset(that.getLength())) > 0)
361 return false;
362 return true;
363 }
364
365 /**
366 * Returns true if this instruction pointer refers to the same location
367 * as the given instruction pointer, false otherwise.
368 * @param that instruction pointer to compare to
369 * @return true if the instruction pointers are equal, false otherwise
370 */
371 public boolean equals(InstructionPointer that) {
372 return this.ip.difference(that.ip) == 0;
373 }
374
375 /**
376 * Compares this instruction pointer with the given object
377 * (InstructionPointer or jq_CompiledCode).
378 * @param that object to compare with
379 * @return true if these objects are equal, false otherwise
380 */
381 public boolean equals(Object that) {
382 if (that instanceof jq_CompiledCode)
383 return equals((jq_CompiledCode) that);
384 else
385 return equals((InstructionPointer) that);
386 }
387
388 /**
389 * Returns the hash code of this instruction pointer.
390 * This is a really bad implementation (just returns 0), and
391 * should not be counted on.
392 * @return hash code
393 */
394 public int hashCode() { return 0; }
395
396 public static final jq_InstanceField _ip;
397 static {
398 jq_Class k = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("LAllocator/CodeAllocator$InstructionPointer;");
399 _ip = k.getOrCreateInstanceField("ip", "I");
400 }
401 }
402
403 public static final jq_StaticField _lowAddress;
404 public static final jq_StaticField _highAddress;
405 static {
406 jq_Class k = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("LAllocator/CodeAllocator;");
407 _lowAddress = k.getOrCreateStaticField("lowAddress", "LMemory/CodeAddress;");
408 _highAddress = k.getOrCreateStaticField("highAddress", "LMemory/CodeAddress;");
409 }
410 }