1 /*
2 * Copyright (c) 2003, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.java.util.jar.pack;
27
28 import com.sun.java.util.jar.pack.ConstantPool.Entry;
29 import java.util.AbstractCollection;
30 import java.util.ArrayList;
31 import java.util.Collection;
32 import java.util.Iterator;
33
34 /**
35 * Collection of relocatable constant pool references.
36 * It operates with respect to a particular byte array,
37 * and stores some of its state in the bytes themselves.
38 * <p>
39 * As a Collection, it can be iterated over, but it is not a List,
40 * since it does not natively support indexed access.
41 * <p>
42 *
43 * @author John Rose
44 */
45 class Fixups extends AbstractCollection implements Constants {
46 byte[] bytes; // the subject of the relocations
47 int head; // desc locating first reloc
48 int tail; // desc locating last reloc
49 int size; // number of relocations
50 Entry[] entries; // [0..size-1] relocations
51 int[] bigDescs; // descs which cannot be stored in the bytes
52
53 // A "desc" (descriptor) is a bit-encoded pair of a location
54 // and format. Every fixup occurs at a "desc". Until final
55 // patching, bytes addressed by descs may also be used to
56 // link this data structure together. If the bytes are missing,
57 // or if the "desc" is too large to encode in the bytes,
58 // it is kept in the bigDescs array.
59
60 Fixups(byte[] bytes) {
61 this.bytes = bytes;
62 entries = new Entry[3];
63 bigDescs = noBigDescs;
64 }
65 Fixups() {
66 // If there are no bytes, all descs are kept in bigDescs.
67 this((byte[])null);
68 }
69 Fixups(byte[] bytes, Collection fixups) {
70 this(bytes);
71 addAll(fixups);
72 }
73 Fixups(Collection fixups) {
74 this((byte[])null);
75 addAll(fixups);
76 }
77
78 private static final int MINBIGSIZE = 1;
79 // cleverly share empty bigDescs:
80 private static int[] noBigDescs = {MINBIGSIZE};
81
82 public int size() {
83 return size;
84 }
85
86 public void trimToSize() {
87 if (size != entries.length) {
88 Entry[] oldEntries = entries;
89 entries = new Entry[size];
90 System.arraycopy(oldEntries, 0, entries, 0, size);
91 }
92 int bigSize = bigDescs[BIGSIZE];
93 if (bigSize == MINBIGSIZE) {
94 bigDescs = noBigDescs;
95 } else if (bigSize != bigDescs.length) {
96 int[] oldBigDescs = bigDescs;
97 bigDescs = new int[bigSize];
98 System.arraycopy(oldBigDescs, 0, bigDescs, 0, bigSize);
99 }
100 }
101
102 public void visitRefs(Collection refs) {
103 for (int i = 0; i < size; i++) {
104 refs.add(entries[i]);
105 }
106 }
107
108 public void clear() {
109 if (bytes != null) {
110 // Clean the bytes:
111 for (Iterator i = iterator(); i.hasNext(); ) {
112 Fixup fx = (Fixup) i.next();
113 //System.out.println("clean "+fx);
114 storeIndex(fx.location(), fx.format(), 0);
115 }
116 }
117 size = 0;
118 if (bigDescs != noBigDescs)
119 bigDescs[BIGSIZE] = MINBIGSIZE;
120 // do not trim to size, however
121 }
122
123 public byte[] getBytes() {
124 return bytes;
125 }
126
127 public void setBytes(byte[] newBytes) {
128 if (bytes == newBytes) return;
129 ArrayList old = null;
130 assert((old = new ArrayList(this)) != null);
131 if (bytes == null || newBytes == null) {
132 // One or the other representations is deficient.
133 // Construct a checkpoint.
134 ArrayList save = new ArrayList(this);
135 clear();
136 bytes = newBytes;
137 addAll(save);
138 } else {
139 // assume newBytes is some sort of bitwise copy of the old bytes
140 bytes = newBytes;
141 }
142 assert(old.equals(new ArrayList(this)));
143 }
144
145 static final int LOC_SHIFT = 1;
146 static final int FMT_MASK = 0x1;
147 static final byte UNUSED_BYTE = 0;
148 static final byte OVERFLOW_BYTE = -1;
149 // fill pointer of bigDescs array is in element [0]
150 static final int BIGSIZE = 0;
151
152 // Format values:
153 public static final int U2_FORMAT = 0;
154 public static final int U1_FORMAT = 1;
155
156 // Special values for the static methods.
157 private static final int SPECIAL_LOC = 0;
158 private static final int SPECIAL_FMT = U2_FORMAT;
159
160 static int fmtLen(int fmt) { return 1+(fmt-U1_FORMAT)/(U2_FORMAT-U1_FORMAT); }
161 static int descLoc(int desc) { return desc >>> LOC_SHIFT; }
162 static int descFmt(int desc) { return desc & FMT_MASK; }
163 static int descEnd(int desc) { return descLoc(desc) + fmtLen(descFmt(desc)); }
164 static int makeDesc(int loc, int fmt) {
165 int desc = (loc << LOC_SHIFT) | fmt;
166 assert(descLoc(desc) == loc);
167 assert(descFmt(desc) == fmt);
168 return desc;
169 }
170 int fetchDesc(int loc, int fmt) {
171 byte b1 = bytes[loc];
172 assert(b1 != OVERFLOW_BYTE);
173 int value;
174 if (fmt == U2_FORMAT) {
175 byte b2 = bytes[loc+1];
176 value = ((b1 & 0xFF) << 8) + (b2 & 0xFF);
177 } else {
178 value = (b1 & 0xFF);
179 }
180 // Stored loc field is difference between its own loc and next loc.
181 return value + (loc << LOC_SHIFT);
182 }
183 boolean storeDesc(int loc, int fmt, int desc) {
184 if (bytes == null)
185 return false;
186 int value = desc - (loc << LOC_SHIFT);
187 byte b1, b2;
188 switch (fmt) {
189 case U2_FORMAT:
190 assert(bytes[loc+0] == UNUSED_BYTE);
191 assert(bytes[loc+1] == UNUSED_BYTE);
192 b1 = (byte)(value >> 8);
193 b2 = (byte)(value >> 0);
194 if (value == (value & 0xFFFF) && b1 != OVERFLOW_BYTE) {
195 bytes[loc+0] = b1;
196 bytes[loc+1] = b2;
197 assert(fetchDesc(loc, fmt) == desc);
198 return true;
199 }
200 break;
201 case U1_FORMAT:
202 assert(bytes[loc] == UNUSED_BYTE);
203 b1 = (byte)value;
204 if (value == (value & 0xFF) && b1 != OVERFLOW_BYTE) {
205 bytes[loc] = b1;
206 assert(fetchDesc(loc, fmt) == desc);
207 return true;
208 }
209 break;
210 default: assert(false);
211 }
212 // Failure. Caller must allocate a bigDesc.
213 bytes[loc] = OVERFLOW_BYTE;
214 assert(fmt==U1_FORMAT || (bytes[loc+1]=(byte)bigDescs[BIGSIZE])!=999);
215 return false;
216 }
217 void storeIndex(int loc, int fmt, int value) {
218 storeIndex(bytes, loc, fmt, value);
219 }
220 static
221 void storeIndex(byte[] bytes, int loc, int fmt, int value) {
222 switch (fmt) {
223 case U2_FORMAT:
224 assert(value == (value & 0xFFFF)) : (value);
225 bytes[loc+0] = (byte)(value >> 8);
226 bytes[loc+1] = (byte)(value >> 0);
227 break;
228 case U1_FORMAT:
229 assert(value == (value & 0xFF)) : (value);
230 bytes[loc] = (byte)value;
231 break;
232 default: assert(false);
233 }
234 }
235
236 /** Simple and necessary tuple to present each fixup. */
237 public static
238 class Fixup implements Comparable {
239 int desc; // location and format of reloc
240 Entry entry; // which entry to plug into the bytes
241 Fixup(int desc, Entry entry) {
242 this.desc = desc;
243 this.entry = entry;
244 }
245 public Fixup(int loc, int fmt, Entry entry) {
246 this.desc = makeDesc(loc, fmt);
247 this.entry = entry;
248 }
249 public int location() { return descLoc(desc); }
250 public int format() { return descFmt(desc); }
251 public Entry entry() { return entry; }
252 public int compareTo(Fixup that) {
253 // Ordering depends only on location.
254 return this.location() - that.location();
255 }
256 public int compareTo(Object that) {
257 return compareTo((Fixup)that);
258 }
259 public boolean equals(Object x) {
260 if (!(x instanceof Fixup)) return false;
261 Fixup that = (Fixup) x;
262 return this.desc == that.desc && this.entry == that.entry;
263 }
264 public String toString() {
265 return "@"+location()+(format()==U1_FORMAT?".1":"")+"="+entry;
266 }
267 }
268
269 private
270 class Itr implements Iterator {
271 int index = 0; // index into entries
272 int bigIndex = BIGSIZE+1; // index into bigDescs
273 int next = head; // desc pointing to next fixup
274 public boolean hasNext() { return index < size; }
275 public void remove() { throw new UnsupportedOperationException(); }
276 public Object next() {
277 int thisIndex = index;
278 return new Fixup(nextDesc(), entries[thisIndex]);
279 }
280 int nextDesc() {
281 int thisIndex = index++;
282 int thisDesc = next;
283 if (index < size) {
284 // Fetch next desc eagerly, in case this fixup gets finalized.
285 int loc = descLoc(thisDesc);
286 int fmt = descFmt(thisDesc);
287 if (bytes != null && bytes[loc] != OVERFLOW_BYTE) {
288 next = fetchDesc(loc, fmt);
289 } else {
290 // The unused extra byte is "asserted" to be equal to BI.
291 // This helps keep the overflow descs in sync.
292 assert(fmt==U1_FORMAT || bytes == null || bytes[loc+1]==(byte)bigIndex);
293 next = bigDescs[bigIndex++];
294 }
295 }
296 return thisDesc;
297 }
298 }
299
300 public Iterator iterator() {
301 return new Itr();
302 }
303 public void add(int location, int format, Entry entry) {
304 addDesc(makeDesc(location, format), entry);
305 }
306 public boolean add(Fixup f) {
307 addDesc(f.desc, f.entry);
308 return true;
309 }
310 public boolean add(Object fixup) {
311 return add((Fixup) fixup);
312 }
313 public boolean addAll(Collection c) {
314 if (c instanceof Fixups) {
315 // Use knowledge of Itr structure to avoid building little structs.
316 Fixups that = (Fixups) c;
317 if (that.size == 0) return false;
318 if (this.size == 0 && entries.length < that.size)
319 growEntries(that.size); // presize exactly
320 Entry[] thatEntries = that.entries;
321 for (Itr i = that.new Itr(); i.hasNext(); ) {
322 int ni = i.index;
323 addDesc(i.nextDesc(), thatEntries[ni]);
324 }
325 return true;
326 } else {
327 return super.addAll(c);
328 }
329 }
330 // Here is how things get added:
331 private void addDesc(int thisDesc, Entry entry) {
332 if (entries.length == size)
333 growEntries(size * 2);
334 entries[size] = entry;
335 if (size == 0) {
336 head = tail = thisDesc;
337 } else {
338 int prevDesc = tail;
339 // Store new desc in previous tail.
340 int prevLoc = descLoc(prevDesc);
341 int prevFmt = descFmt(prevDesc);
342 int prevLen = fmtLen(prevFmt);
343 int thisLoc = descLoc(thisDesc);
344 // The collection must go in ascending order, and not overlap.
345 if (thisLoc < prevLoc + prevLen)
346 badOverlap(thisLoc);
347 tail = thisDesc;
348 if (!storeDesc(prevLoc, prevFmt, thisDesc)) {
349 // overflow
350 int bigSize = bigDescs[BIGSIZE];
351 if (bigDescs.length == bigSize)
352 growBigDescs();
353 //System.out.println("bigDescs["+bigSize+"] = "+thisDesc);
354 bigDescs[bigSize++] = thisDesc;
355 bigDescs[BIGSIZE] = bigSize;
356 }
357 }
358 size += 1;
359 }
360 private void badOverlap(int thisLoc) {
361 throw new IllegalArgumentException("locs must be ascending and must not overlap: "+thisLoc+" >> "+this);
362 }
363
364 private void growEntries(int newSize) {
365 Entry[] oldEntries = entries;
366 entries = new Entry[Math.max(3, newSize)];
367 System.arraycopy(oldEntries, 0, entries, 0, oldEntries.length);
368 }
369 private void growBigDescs() {
370 int[] oldBigDescs = bigDescs;
371 bigDescs = new int[oldBigDescs.length * 2];
372 System.arraycopy(oldBigDescs, 0, bigDescs, 0, oldBigDescs.length);
373 }
374
375 /// Static methods that optimize the use of this class.
376 public static
377 Object add(Object prevFixups,
378 byte[] bytes, int loc, int fmt,
379 Entry e) {
380 Fixups f;
381 if (prevFixups == null) {
382 if (loc == SPECIAL_LOC && fmt == SPECIAL_FMT) {
383 // Special convention: If the attribute has a
384 // U2 relocation at position zero, store the Entry
385 // rather than building a Fixups structure.
386 return e;
387 }
388 f = new Fixups(bytes);
389 } else if (!(prevFixups instanceof Fixups)) {
390 // Recognize the special convention:
391 Entry firstEntry = (Entry) prevFixups;
392 f = new Fixups(bytes);
393 f.add(SPECIAL_LOC, SPECIAL_FMT, firstEntry);
394 } else {
395 f = (Fixups) prevFixups;
396 assert(f.bytes == bytes);
397 }
398 f.add(loc, fmt, e);
399 return f;
400 }
401
402 public static
403 void setBytes(Object fixups, byte[] bytes) {
404 if (fixups instanceof Fixups) {
405 Fixups f = (Fixups) fixups;
406 f.setBytes(bytes);
407 }
408 }
409
410 public static
411 Object trimToSize(Object fixups) {
412 if (fixups instanceof Fixups) {
413 Fixups f = (Fixups) fixups;
414 f.trimToSize();
415 if (f.size() == 0)
416 fixups = null;
417 }
418 return fixups;
419 }
420
421 // Iterate over all the references in this set of fixups.
422 public static
423 void visitRefs(Object fixups, Collection refs) {
424 if (fixups == null) {
425 } else if (!(fixups instanceof Fixups)) {
426 // Special convention; see above.
427 refs.add((Entry) fixups);
428 } else {
429 Fixups f = (Fixups) fixups;
430 f.visitRefs(refs);
431 }
432 }
433
434 // Clear out this set of fixups by replacing each reference
435 // by a hardcoded coding of its reference, drawn from ix.
436 public static
437 void finishRefs(Object fixups, byte[] bytes, ConstantPool.Index ix) {
438 if (fixups == null)
439 return;
440 if (!(fixups instanceof Fixups)) {
441 // Special convention; see above.
442 int index = ix.indexOf((Entry) fixups);
443 storeIndex(bytes, SPECIAL_LOC, SPECIAL_FMT, index);
444 return;
445 }
446 Fixups f = (Fixups) fixups;
447 assert(f.bytes == bytes);
448 f.finishRefs(ix);
449 }
450
451 void finishRefs(ConstantPool.Index ix) {
452 if (isEmpty())
453 return;
454 for (Iterator i = iterator(); i.hasNext(); ) {
455 Fixup fx = (Fixup) i.next();
456 int index = ix.indexOf(fx.entry);
457 //System.out.println("finish "+fx+" = "+index);
458 // Note that the iterator has already fetched the
459 // bytes we are about to overwrite.
460 storeIndex(fx.location(), fx.format(), index);
461 }
462 // Further iterations should do nothing:
463 bytes = null; // do not clean them
464 clear();
465 }
466
467 /*
468 /// Testing.
469 public static void main(String[] av) {
470 byte[] bytes = new byte[1 << 20];
471 ConstantPool cp = new ConstantPool();
472 Fixups f = new Fixups(bytes);
473 boolean isU1 = false;
474 int span = 3;
475 int nextLoc = 0;
476 int[] locs = new int[100];
477 final int[] indexes = new int[100];
478 int iptr = 1;
479 for (int loc = 0; loc < bytes.length; loc++) {
480 if (loc == nextLoc && loc+1 < bytes.length) {
481 int fmt = (isU1 ? U1_FORMAT : U2_FORMAT);
482 Entry e = ConstantPool.getUtf8Entry("L"+loc);
483 f.add(loc, fmt, e);
484 isU1 ^= true;
485 if (iptr < 10) {
486 // Make it close in.
487 nextLoc += fmtLen(fmt) + (iptr < 5 ? 0 : 1);
488 } else {
489 nextLoc += span;
490 span = (int)(span * 1.77);
491 }
492 // Here are the bytes that would have gone here:
493 locs[iptr] = loc;
494 if (fmt == U1_FORMAT) {
495 indexes[iptr++] = (loc & 0xFF);
496 } else {
497 indexes[iptr++] = ((loc & 0xFF) << 8) | ((loc+1) & 0xFF);
498 ++loc; // skip a byte
499 }
500 continue;
501 }
502 bytes[loc] = (byte)loc;
503 }
504 System.out.println("size="+f.size()
505 +" overflow="+(f.bigDescs[BIGSIZE]-1));
506 System.out.println("Fixups: "+f);
507 // Test collection contents.
508 assert(iptr == 1+f.size());
509 List l = new ArrayList(f);
510 Collections.sort(l); // should not change the order
511 if (!l.equals(new ArrayList(f))) System.out.println("** disordered");
512 f.setBytes(null);
513 if (!l.equals(new ArrayList(f))) System.out.println("** bad set 1");
514 f.setBytes(bytes);
515 if (!l.equals(new ArrayList(f))) System.out.println("** bad set 2");
516 Fixups f3 = new Fixups(f);
517 if (!l.equals(new ArrayList(f3))) System.out.println("** bad set 3");
518 Iterator fi = f.iterator();
519 for (int i = 1; i < iptr; i++) {
520 Fixup fx = (Fixup) fi.next();
521 if (fx.location() != locs[i]) {
522 System.out.println("** "+fx+" != "+locs[i]);
523 }
524 if (fx.format() == U1_FORMAT)
525 System.out.println(fx+" -> "+bytes[locs[i]]);
526 else
527 System.out.println(fx+" -> "+bytes[locs[i]]+" "+bytes[locs[i]+1]);
528 }
529 assert(!fi.hasNext());
530 indexes[0] = 1; // like iptr
531 Index ix = new Index("ix") {
532 public int indexOf(Entry e) {
533 return indexes[indexes[0]++];
534 }
535 };
536 f.finishRefs(ix);
537 for (int loc = 0; loc < bytes.length; loc++) {
538 if (bytes[loc] != (byte)loc) {
539 System.out.println("** ["+loc+"] = "+bytes[loc]+" != "+(byte)loc);
540 }
541 }
542 }
543 //*/
544 }