1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.reftable;
12
13 import static java.nio.charset.StandardCharsets.UTF_8;
14 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN;
15 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
16 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
17 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_DATA;
18 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_NONE;
19 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_RESTARTS;
20 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE;
21 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
22 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_1ID;
23 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_2ID;
24 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_NONE;
25 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_SYMREF;
26 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TYPE_MASK;
27 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.reverseUpdateIndex;
28 import static org.eclipse.jgit.internal.storage.reftable.ReftableOutputStream.computeVarintSize;
29 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
30 import static org.eclipse.jgit.lib.Ref.Storage.NEW;
31
32 import java.io.IOException;
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.List;
36
37 import org.eclipse.jgit.internal.JGitText;
38 import org.eclipse.jgit.lib.ObjectId;
39 import org.eclipse.jgit.lib.PersonIdent;
40 import org.eclipse.jgit.lib.Ref;
41 import org.eclipse.jgit.util.IntList;
42 import org.eclipse.jgit.util.LongList;
43 import org.eclipse.jgit.util.NB;
44
45
46 class BlockWriter {
47 private final byte blockType;
48 private final byte keyType;
49 private final List<Entry> entries;
50 private final int blockLimitBytes;
51 private final int restartInterval;
52
53 private int entriesSumBytes;
54 private int restartCnt;
55
56 BlockWriter(byte type, byte kt, int bs, int ri) {
57 blockType = type;
58 keyType = kt;
59 blockLimitBytes = bs;
60 restartInterval = ri;
61 entries = new ArrayList<>(estimateEntryCount(type, kt, bs));
62 }
63
64 private static int estimateEntryCount(byte blockType, byte keyType,
65 int blockLimitBytes) {
66 double avgBytesPerEntry;
67 switch (blockType) {
68 case REF_BLOCK_TYPE:
69 default:
70 avgBytesPerEntry = 35.31;
71 break;
72
73 case OBJ_BLOCK_TYPE:
74 avgBytesPerEntry = 4.19;
75 break;
76
77 case LOG_BLOCK_TYPE:
78 avgBytesPerEntry = 101.14;
79 break;
80
81 case INDEX_BLOCK_TYPE:
82 switch (keyType) {
83 case REF_BLOCK_TYPE:
84 case LOG_BLOCK_TYPE:
85 default:
86 avgBytesPerEntry = 27.44;
87 break;
88
89 case OBJ_BLOCK_TYPE:
90 avgBytesPerEntry = 11.57;
91 break;
92 }
93 }
94
95 int cnt = (int) (Math.ceil(blockLimitBytes / avgBytesPerEntry));
96 return Math.min(cnt, 4096);
97 }
98
99 byte blockType() {
100 return blockType;
101 }
102
103 boolean padBetweenBlocks() {
104 return padBetweenBlocks(blockType)
105 || (blockType == INDEX_BLOCK_TYPE && padBetweenBlocks(keyType));
106 }
107
108 static boolean padBetweenBlocks(byte type) {
109 return type == REF_BLOCK_TYPE || type == OBJ_BLOCK_TYPE;
110 }
111
112 byte[] lastKey() {
113 return entries.get(entries.size() - 1).key;
114 }
115
116 int currentSize() {
117 return computeBlockBytes(0, false);
118 }
119
120 void mustAdd(Entry entry) throws BlockSizeTooSmallException {
121 if (!tryAdd(entry, true)) {
122
123 throw blockSizeTooSmall(entry);
124 }
125 }
126
127 boolean tryAdd(Entry entry) {
128 if (entry instanceof ObjEntry
129 && computeBlockBytes(entry.sizeBytes(), 1) > blockLimitBytes) {
130
131
132
133
134
135 ((ObjEntry) entry).markScanRequired();
136 }
137
138 if (tryAdd(entry, true)) {
139 return true;
140 } else if (nextShouldBeRestart()) {
141
142
143
144
145 return tryAdd(entry, false);
146 }
147 return false;
148 }
149
150 private boolean tryAdd(Entry entry, boolean tryRestart) {
151 byte[] key = entry.key;
152 int prefixLen = 0;
153 boolean restart = tryRestart && nextShouldBeRestart();
154 if (!restart) {
155 Entry priorEntry = entries.get(entries.size() - 1);
156 byte[] prior = priorEntry.key;
157 prefixLen = commonPrefix(prior, prior.length, key);
158 if (prefixLen <= 5 && keyType == REF_BLOCK_TYPE) {
159
160
161 restart = true;
162 prefixLen = 0;
163 } else if (prefixLen == 0) {
164 restart = true;
165 }
166 }
167
168 entry.restart = restart;
169 entry.prefixLen = prefixLen;
170 int entryBytes = entry.sizeBytes();
171 if (computeBlockBytes(entryBytes, restart) > blockLimitBytes) {
172 return false;
173 }
174
175 entriesSumBytes += entryBytes;
176 entries.add(entry);
177 if (restart) {
178 restartCnt++;
179 }
180 return true;
181 }
182
183 private boolean nextShouldBeRestart() {
184 int cnt = entries.size();
185 return (cnt == 0 || ((cnt + 1) % restartInterval) == 0)
186 && restartCnt < MAX_RESTARTS;
187 }
188
189 private int computeBlockBytes(int entryBytes, boolean restart) {
190 return computeBlockBytes(
191 entriesSumBytes + entryBytes,
192 restartCnt + (restart ? 1 : 0));
193 }
194
195 private static int computeBlockBytes(int entryBytes, int restartCnt) {
196 return 4
197 + entryBytes
198 + restartCnt * 3
199 + 2;
200 }
201
202 void writeTo(ReftableOutputStream os) throws IOException {
203 os.beginBlock(blockType);
204 IntList restarts = new IntList(restartCnt);
205 for (Entry entry : entries) {
206 if (entry.restart) {
207 restarts.add(os.bytesWrittenInBlock());
208 }
209 entry.writeKey(os);
210 entry.writeValue(os);
211 }
212 if (restarts.size() == 0 || restarts.size() > MAX_RESTARTS) {
213 throw new IllegalStateException();
214 }
215 for (int i = 0; i < restarts.size(); i++) {
216 os.writeInt24(restarts.get(i));
217 }
218 os.writeInt16(restarts.size());
219 os.flushBlock();
220 }
221
222 private BlockSizeTooSmallException blockSizeTooSmall(Entry entry) {
223
224 int min = FILE_HEADER_LEN + computeBlockBytes(entry.sizeBytes(), 1);
225 return new BlockSizeTooSmallException(min);
226 }
227
228 static int commonPrefix(byte[] a, int n, byte[] b) {
229 int len = Math.min(n, Math.min(a.length, b.length));
230 for (int i = 0; i < len; i++) {
231 if (a[i] != b[i]) {
232 return i;
233 }
234 }
235 return len;
236 }
237
238 static int encodeSuffixAndType(int sfx, int valueType) {
239 return (sfx << 3) | valueType;
240 }
241
242 static int compare(
243 byte[] a, int ai, int aLen,
244 byte[] b, int bi, int bLen) {
245 int aEnd = ai + aLen;
246 int bEnd = bi + bLen;
247 while (ai < aEnd && bi < bEnd) {
248 int c = (a[ai++] & 0xff) - (b[bi++] & 0xff);
249 if (c != 0) {
250 return c;
251 }
252 }
253 return aLen - bLen;
254 }
255
256 abstract static class Entry {
257 static int compare(Entry ea, Entry eb) {
258 byte[] a = ea.key;
259 byte[] b = eb.key;
260 return BlockWriter.compare(a, 0, a.length, b, 0, b.length);
261 }
262
263 final byte[] key;
264 int prefixLen;
265 boolean restart;
266
267 Entry(byte[] key) {
268 this.key = key;
269 }
270
271 void writeKey(ReftableOutputStream os) {
272 int sfxLen = key.length - prefixLen;
273 os.writeVarint(prefixLen);
274 os.writeVarint(encodeSuffixAndType(sfxLen, valueType()));
275 os.write(key, prefixLen, sfxLen);
276 }
277
278 int sizeBytes() {
279 int sfxLen = key.length - prefixLen;
280 int sfx = encodeSuffixAndType(sfxLen, valueType());
281 return computeVarintSize(prefixLen)
282 + computeVarintSize(sfx)
283 + sfxLen
284 + valueSize();
285 }
286
287 abstract byte blockType();
288 abstract int valueType();
289 abstract int valueSize();
290 abstract void writeValue(ReftableOutputStream os) throws IOException;
291 }
292
293 static class IndexEntry extends Entry {
294 private final long blockPosition;
295
296 IndexEntry(byte[] key, long blockPosition) {
297 super(key);
298 this.blockPosition = blockPosition;
299 }
300
301 @Override
302 byte blockType() {
303 return INDEX_BLOCK_TYPE;
304 }
305
306 @Override
307 int valueType() {
308 return 0;
309 }
310
311 @Override
312 int valueSize() {
313 return computeVarintSize(blockPosition);
314 }
315
316 @Override
317 void writeValue(ReftableOutputStream os) {
318 os.writeVarint(blockPosition);
319 }
320 }
321
322 static class RefEntry extends Entry {
323 final Ref ref;
324 final long updateIndexDelta;
325
326 RefEntry(Ref ref, long updateIndexDelta) {
327 super(nameUtf8(ref));
328 this.ref = ref;
329 this.updateIndexDelta = updateIndexDelta;
330 }
331
332 @Override
333 byte blockType() {
334 return REF_BLOCK_TYPE;
335 }
336
337 @Override
338 int valueType() {
339 if (ref.isSymbolic()) {
340 return VALUE_SYMREF;
341 } else if (ref.getStorage() == NEW && ref.getObjectId() == null) {
342 return VALUE_NONE;
343 } else if (ref.getPeeledObjectId() != null) {
344 return VALUE_2ID;
345 } else {
346 return VALUE_1ID;
347 }
348 }
349
350 @Override
351 int valueSize() {
352 int n = computeVarintSize(updateIndexDelta);
353 switch (valueType()) {
354 case VALUE_NONE:
355 return n;
356 case VALUE_1ID:
357 return n + OBJECT_ID_LENGTH;
358 case VALUE_2ID:
359 return n + 2 * OBJECT_ID_LENGTH;
360 case VALUE_SYMREF:
361 if (ref.isSymbolic()) {
362 int nameLen = nameUtf8(ref.getTarget()).length;
363 return n + computeVarintSize(nameLen) + nameLen;
364 }
365 }
366 throw new IllegalStateException();
367 }
368
369 @Override
370 void writeValue(ReftableOutputStream os) throws IOException {
371 os.writeVarint(updateIndexDelta);
372 switch (valueType()) {
373 case VALUE_NONE:
374 return;
375
376 case VALUE_1ID: {
377 ObjectId id1 = ref.getObjectId();
378 if (!ref.isPeeled()) {
379 throw new IOException(JGitText.get().peeledRefIsRequired);
380 } else if (id1 == null) {
381 throw new IOException(JGitText.get().invalidId0);
382 }
383 os.writeId(id1);
384 return;
385 }
386
387 case VALUE_2ID: {
388 ObjectId id1 = ref.getObjectId();
389 ObjectId id2 = ref.getPeeledObjectId();
390 if (!ref.isPeeled()) {
391 throw new IOException(JGitText.get().peeledRefIsRequired);
392 } else if (id1 == null || id2 == null) {
393 throw new IOException(JGitText.get().invalidId0);
394 }
395 os.writeId(id1);
396 os.writeId(id2);
397 return;
398 }
399
400 case VALUE_SYMREF:
401 if (ref.isSymbolic()) {
402 os.writeVarintString(ref.getTarget().getName());
403 return;
404 }
405 }
406 throw new IllegalStateException();
407 }
408
409 private static byte[] nameUtf8(Ref ref) {
410 return ref.getName().getBytes(UTF_8);
411 }
412 }
413
414 static class ObjEntry extends Entry {
415 final LongList blockPos;
416
417 ObjEntry(int idLen, ObjectId id, LongList blockPos) {
418 super(key(idLen, id));
419 this.blockPos = blockPos;
420 }
421
422 private static byte[] key(int idLen, ObjectId id) {
423 byte[] key = new byte[OBJECT_ID_LENGTH];
424 id.copyRawTo(key, 0);
425 if (idLen < OBJECT_ID_LENGTH) {
426 return Arrays.copyOf(key, idLen);
427 }
428 return key;
429 }
430
431 void markScanRequired() {
432 blockPos.clear();
433 }
434
435 @Override
436 byte blockType() {
437 return OBJ_BLOCK_TYPE;
438 }
439
440 @Override
441 int valueType() {
442 int cnt = blockPos.size();
443 return cnt != 0 && cnt <= VALUE_TYPE_MASK ? cnt : 0;
444 }
445
446 @Override
447 int valueSize() {
448 int cnt = blockPos.size();
449 if (cnt == 0) {
450 return computeVarintSize(0);
451 }
452
453 int n = 0;
454 if (cnt > VALUE_TYPE_MASK) {
455 n += computeVarintSize(cnt);
456 }
457 n += computeVarintSize(blockPos.get(0));
458 for (int j = 1; j < cnt; j++) {
459 long prior = blockPos.get(j - 1);
460 long b = blockPos.get(j);
461 n += computeVarintSize(b - prior);
462 }
463 return n;
464 }
465
466 @Override
467 void writeValue(ReftableOutputStream os) throws IOException {
468 int cnt = blockPos.size();
469 if (cnt == 0) {
470 os.writeVarint(0);
471 return;
472 }
473
474 if (cnt > VALUE_TYPE_MASK) {
475 os.writeVarint(cnt);
476 }
477 os.writeVarint(blockPos.get(0));
478 for (int j = 1; j < cnt; j++) {
479 long prior = blockPos.get(j - 1);
480 long b = blockPos.get(j);
481 os.writeVarint(b - prior);
482 }
483 }
484 }
485
486 static class DeleteLogEntry extends Entry {
487 DeleteLogEntry(String refName, long updateIndex) {
488 super(LogEntry.key(refName, updateIndex));
489 }
490
491 @Override
492 byte blockType() {
493 return LOG_BLOCK_TYPE;
494 }
495
496 @Override
497 int valueType() {
498 return LOG_NONE;
499 }
500
501 @Override
502 int valueSize() {
503 return 0;
504 }
505
506 @Override
507 void writeValue(ReftableOutputStream os) {
508
509 }
510 }
511
512 static class LogEntry extends Entry {
513 final ObjectId oldId;
514 final ObjectId newId;
515 final long timeSecs;
516 final short tz;
517 final byte[] name;
518 final byte[] email;
519 final byte[] msg;
520
521 LogEntry(String refName, long updateIndex, PersonIdent who,
522 ObjectId oldId, ObjectId newId, String message) {
523 super(key(refName, updateIndex));
524
525 this.oldId = oldId;
526 this.newId = newId;
527 this.timeSecs = who.getWhen().getTime() / 1000L;
528 this.tz = (short) who.getTimeZoneOffset();
529 this.name = who.getName().getBytes(UTF_8);
530 this.email = who.getEmailAddress().getBytes(UTF_8);
531 this.msg = message.getBytes(UTF_8);
532 }
533
534 static byte[] key(String ref, long index) {
535 byte[] name = ref.getBytes(UTF_8);
536 byte[] key = Arrays.copyOf(name, name.length + 1 + 8);
537 NB.encodeInt64(key, key.length - 8, reverseUpdateIndex(index));
538 return key;
539 }
540
541 @Override
542 byte blockType() {
543 return LOG_BLOCK_TYPE;
544 }
545
546 @Override
547 int valueType() {
548 return LOG_DATA;
549 }
550
551 @Override
552 int valueSize() {
553 return 2 * OBJECT_ID_LENGTH
554 + computeVarintSize(name.length) + name.length
555 + computeVarintSize(email.length) + email.length
556 + computeVarintSize(timeSecs)
557 + 2
558 + computeVarintSize(msg.length) + msg.length;
559 }
560
561 @Override
562 void writeValue(ReftableOutputStream os) {
563 os.writeId(oldId);
564 os.writeId(newId);
565 os.writeVarintString(name);
566 os.writeVarintString(email);
567 os.writeVarint(timeSecs);
568 os.writeInt16(tz);
569 os.writeVarintString(msg);
570 }
571 }
572 }