Sitelet https://github.com/ArcadeData/arcadedb/commit/1d6d683140d50ae03293e463ddcb66c6c0cb1ba0
Skip to content

Commit 1d6d683

Browse files
lvcalvca
committed
fix: infinite loop on LSMTree indexes when iterating DESC
Fixed issue #3964 Added more safeguards against infinite loops in case of corruption
1 parent 2748dde commit 1d6d683

12 files changed

Lines changed: 362 additions & 2 deletions

‎engine/src/main/java/com/arcadedb/index/CompressedAny2RIDIndex.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -157,7 +157,11 @@ public RID get(final Binary threadBuffer, final Object key) {
157157
return null;
158158

159159
// SLOT OCCUPIED, CHECK FOR THE KEY
160+
// Termination invariant: each iteration either returns (key found), breaks
161+
// (chain terminator), or jumps to a strictly greater nextPos because put()
162+
// always appends new entries at chunk.size().
160163
threadBuffer.position(pos);
164+
int lastChainPos = pos;
161165
while (true) {
162166
final Object slotKey = serializer.deserializeValue(database, threadBuffer, keyBinaryType, null);
163167

@@ -170,6 +174,8 @@ public RID get(final Binary threadBuffer, final Object key) {
170174
if (nextPos <= 0)
171175
break;
172176

177+
assert nextPos > lastChainPos : "CompressedAny2RIDIndex.get chain must move forward to terminate";
178+
lastChainPos = nextPos;
173179
threadBuffer.position(nextPos);
174180
}
175181

@@ -205,8 +211,12 @@ public void put(final K key, final RID value) {
205211

206212
} else {
207213
// SLOT OCCUPIED, CHECK FOR THE KEY
214+
// Termination invariant: each iteration either throws (duplicate), breaks
215+
// (chain terminator), or jumps to a strictly greater nextPos because new
216+
// entries are always appended at chunk.size().
208217
chunk.position(pos);
209218
int lastNextPos;
219+
int lastChainPos = pos;
210220
while (true) {
211221
final Object slotKey = serializer.deserializeValue(database, chunk, keyBinaryType, null);
212222

@@ -219,6 +229,8 @@ public void put(final K key, final RID value) {
219229
if (nextPos <= 0)
220230
break;
221231

232+
assert nextPos > lastChainPos : "CompressedAny2RIDIndex.put chain must move forward to terminate";
233+
lastChainPos = nextPos;
222234
chunk.position(nextPos);
223235
}
224236

‎engine/src/main/java/com/arcadedb/index/CompressedRID2RIDIndex.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -176,7 +176,12 @@ public RID get(final RID key) {
176176
return null;
177177

178178
// SLOT OCCUPIED, CHECK FOR THE KEY
179+
// Termination invariant: each iteration either returns (key found), breaks
180+
// (chain terminator nextPos <= 0), or jumps to a strictly greater nextPos
181+
// because put() always appends new entries at chunk.size(). The loop is
182+
// therefore bounded by the number of collisions in this hash bucket.
179183
chunk.position(pos);
184+
int lastChainPos = pos;
180185
while (true) {
181186
final Object slotKey = serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
182187
if (BinaryComparator.equals(slotKey, key)) {
@@ -189,6 +194,8 @@ public RID get(final RID key) {
189194
if (nextPos <= 0)
190195
break;
191196

197+
assert nextPos > lastChainPos : "CompressedRID2RIDIndex.get chain must move forward to terminate";
198+
lastChainPos = nextPos;
192199
chunk.position(nextPos);
193200
}
194201

@@ -227,8 +234,13 @@ public void put(final RID key, final RID valueRID) {
227234

228235
} else {
229236
// SLOT OCCUPIED, CHECK FOR THE KEY
237+
// Termination invariant: each iteration either throws (duplicate key), breaks
238+
// (chain terminator nextPos <= 0), or jumps to a strictly greater nextPos
239+
// because new entries are always appended at chunk.size(). The loop is bounded
240+
// by the number of collisions in this hash bucket.
230241
chunk.position(pos);
231242
int lastNextPos;
243+
int lastChainPos = pos;
232244
while (true) {
233245
final RID slotKey = (RID) serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
234246

@@ -241,6 +253,8 @@ public void put(final RID key, final RID valueRID) {
241253
if (nextPos <= 0)
242254
break;
243255

256+
assert nextPos > lastChainPos : "CompressedRID2RIDIndex.put chain must move forward to terminate";
257+
lastChainPos = nextPos;
244258
chunk.position(nextPos);
245259
}
246260

‎engine/src/main/java/com/arcadedb/index/CompressedRID2RIDsIndex.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -195,7 +195,15 @@ public List<Pair<RID, RID>> get(final RID key) {
195195
return null;
196196

197197
// SLOT OCCUPIED, CHECK FOR THE KEY
198+
// Termination invariants:
199+
// - outer loop: each iteration either returns (key found), breaks (chain
200+
// terminator), or jumps to a strictly greater nextPos (new entries always
201+
// appended at chunk.size()).
202+
// - inner value-list loop: each iteration jumps to a strictly SMALLER
203+
// nextEntryPos because every put() appends the new entry at chunk.size()
204+
// and stores the previous (older, lower-positioned) entry as its back-pointer.
198205
chunk.position(pos);
206+
int lastChainPos = pos;
199207
while (true) {
200208
final Object slotKey = serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
201209

@@ -211,7 +219,10 @@ public List<Pair<RID, RID>> get(final RID key) {
211219
RID vertexRid = (RID) serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
212220
list.add(new Pair<>(edgeRid, vertexRid));
213221

222+
int lastEntryPos = Integer.MAX_VALUE;
214223
while (nextEntryPos > 0) {
224+
assert nextEntryPos < lastEntryPos : "CompressedRID2RIDsIndex value-list must move backward to terminate";
225+
lastEntryPos = nextEntryPos;
215226
chunk.position(nextEntryPos);
216227

217228
edgeRid = (RID) serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
@@ -229,6 +240,8 @@ public List<Pair<RID, RID>> get(final RID key) {
229240
if (nextPos <= 0)
230241
break;
231242

243+
assert nextPos > lastChainPos : "CompressedRID2RIDsIndex.get chain must move forward to terminate";
244+
lastChainPos = nextPos;
232245
chunk.position(nextPos);
233246
}
234247

@@ -271,8 +284,12 @@ public void put(final RID key, final RID edgeRID, final RID vertexRID) {
271284

272285
} else {
273286
// SLOT OCCUPIED, CHECK FOR THE KEY
287+
// Termination invariant: each iteration either returns (key found, after
288+
// appending the new value), breaks (chain terminator), or jumps to a strictly
289+
// greater nextPos (new entries always appended at chunk.size()).
274290
chunk.position(pos);
275291
int lastNextPos;
292+
int lastChainPos = pos;
276293
while (true) {
277294
final RID slotKey = (RID) serializer.deserializeValue(database, chunk, BinaryTypes.TYPE_COMPRESSED_RID, null);
278295

@@ -308,6 +325,8 @@ public void put(final RID key, final RID edgeRID, final RID vertexRID) {
308325
if (nextPos <= 0)
309326
break;
310327

328+
assert nextPos > lastChainPos : "CompressedRID2RIDsIndex.put chain must move forward to terminate";
329+
lastChainPos = nextPos;
311330
chunk.position(nextPos);
312331
}
313332

‎engine/src/main/java/com/arcadedb/index/hash/HashIndexBucket.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -528,6 +528,11 @@ private void insertIntoOverflow(MutablePage currentPage, int currentPageNum,
528528
serializedKey.length + varIntSize(1) + serializedRID.length;
529529
final int totalNeeded = entryDataSize + SLOT_SIZE;
530530

531+
// Defensive cycle detection: a corrupted overflow chain that loops back to a
532+
// previously-seen page would otherwise spin forever. Track visited page numbers.
533+
final java.util.Set<Integer> visited = new java.util.HashSet<>();
534+
visited.add(currentPageNum);
535+
531536
while (true) {
532537
int overflowPageNum = currentPage.readInt(BUCKET_OVERFLOW_PAGE);
533538

@@ -537,6 +542,11 @@ private void insertIntoOverflow(MutablePage currentPage, int currentPageNum,
537542
currentPage.writeInt(BUCKET_OVERFLOW_PAGE, overflowPageNum);
538543
}
539544

545+
if (!visited.add(overflowPageNum))
546+
throw new IllegalStateException(
547+
"Detected cycle in hash index '" + getName() + "' overflow chain at page " + overflowPageNum
548+
+ ". The index is corrupted, please rebuild it.");
549+
540550
final MutablePage overflowPage = database.getTransaction()
541551
.getPageToModify(new PageId(database, fileId, overflowPageNum), pageSize, false);
542552
final int entryCount = overflowPage.readShort(BUCKET_ENTRY_COUNT) & 0xFFFF;
@@ -892,7 +902,15 @@ private void insertEntryInPage(final MutablePage page, final int entryCount, fin
892902
private void insertRawEntry(final int bucketPageNum, final byte[] rawEntry) throws IOException {
893903
int currentPageNum = bucketPageNum;
894904

905+
// Defensive cycle detection on the overflow chain (see insertIntoOverflow above).
906+
final java.util.Set<Integer> visited = new java.util.HashSet<>();
907+
895908
while (true) {
909+
if (!visited.add(currentPageNum))
910+
throw new IllegalStateException(
911+
"Detected cycle in hash index '" + getName() + "' overflow chain at page " + currentPageNum
912+
+ ". The index is corrupted, please rebuild it.");
913+
896914
final MutablePage page = database.getTransaction()
897915
.getPageToModify(new PageId(database, fileId, currentPageNum), pageSize, false);
898916
final int entryCount = page.readShort(BUCKET_ENTRY_COUNT) & 0xFFFF;

‎engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexAbstract.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -319,6 +319,10 @@ protected void writeEntrySingleValue(final Binary buffer, final Object[] keys, f
319319
protected int writeEntryMultipleValues(final Binary buffer, final Object[] keys, Object[] rids, final int availableSpaceInPage,
320320
final int pageUsableSpace, final PageId pageId) {
321321
Object[] values = rids;
322+
// Termination invariant: each iteration either breaks (all values written),
323+
// returns (single value still doesn't fit), or strictly shrinks `values` via
324+
// Arrays.copyOf(values, written) where written < values.length. Therefore the
325+
// loop runs at most O(rids.length) times.
322326
do {
323327
buffer.clear();
324328
writeKeys(buffer, keys);
@@ -340,7 +344,9 @@ protected int writeEntryMultipleValues(final Binary buffer, final Object[] keys,
340344
values.length, pageId, written);
341345

342346
// NOT ENOUGH SPACE: Split the array with the max number of values that fit in the page
347+
final int prevLen = values.length;
343348
values = Arrays.copyOf(values, written);
349+
assert values.length < prevLen : "writeEntryMultipleValues must shrink values each iteration to terminate";
344350

345351
} while (true);
346352

‎engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexCompacted.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,11 @@ public List<MutablePage> appendDuringCompaction(final Binary keyValueContent, Mu
117117
RID[] values = rids;
118118

119119
// REPEAT TO WRITE ALL THE RIDS (SPLIT THEM IF THEY DON'T FIT IN THE CURRENT PAGE)
120+
// Termination invariant: each iteration either breaks (all values written) or
121+
// strictly shrinks `values` via Arrays.copyOfRange(values, writtenValues, values.length)
122+
// where writtenValues > 0 (when 0, writeEntryMultipleValues throws/returns 0 for a
123+
// single value that doesn't fit and we restart on a fresh page). The loop therefore
124+
// runs at most O(rids.length) times.
120125
do {
121126
int writtenValues = writeEntryMultipleValues(keyValueContent, convertedKeys, values, freeSpaceInPage,
122127
currentPage.getMaxContentSize() - getHeaderSize(pageNum), currentPage.getPageId());
@@ -158,7 +163,9 @@ public List<MutablePage> appendDuringCompaction(final Binary keyValueContent, Mu
158163
"Splitting key values. Total values=%d, written values=%d in page %s",
159164
values.length, writtenValues, currentPage.getPageId());
160165

166+
final int prevLen = values.length;
161167
values = Arrays.copyOfRange(values, writtenValues, values.length);
168+
assert values.length < prevLen : "compacted writeNewPages must shrink values each iteration to terminate";
162169

163170
// NO SPACE LEFT, CREATE A NEW PAGE AND FLUSH TO THE DATABASE THE CURRENT ONE (NO WAL)
164171
database.getPageManager().updatePageVersion(currentPage, true);

‎engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexCompactor.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -202,6 +202,9 @@ public boolean compact(final LSMTreeIndex mainIndex) throws IOException, Interru
202202
final LSMTreeIndexUnderlyingPageCursor iter = iterators[idx];
203203

204204
// BROWSE THE SAME ITERATOR TO CHECK IF NEXT VALUES HAVE THE SAME KEY
205+
// Termination invariant: each iteration either breaks (different key, no more
206+
// entries, or iter == null) or strictly advances `iter` via iter.next(). The
207+
// loop is therefore bounded by the number of remaining entries in the page.
205208
while (true) {
206209
if (iter == null)
207210
break;
@@ -220,7 +223,10 @@ public boolean compact(final LSMTreeIndex mainIndex) throws IOException, Interru
220223

221224
// CHECK IF THE NEXT ELEMENT HAS THE SAME KEY
222225
if (iter.hasNext()) {
226+
final int prevPos = iter.getCurrentPositionInPage();
223227
iter.next();
228+
assert iter.getCurrentPositionInPage() != prevPos :
229+
"compactor iterator must advance position on next() to terminate";
224230
keys[idx] = iter.getKeys();
225231

226232
if (LSMTreeIndexMutable.compareKeys(comparator, keyTypes, keys[idx], minorKey) != 0)

‎engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexCursor.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -173,7 +173,18 @@ public LSMTreeIndexCursor(final LSMTreeIndexMutable index, final boolean ascendi
173173
for (int i = 0; i < pageCursors.length; ++i) {
174174

175175
LSMTreeIndexUnderlyingAbstractCursor pageCursor = pageCursors[i];
176+
// Defensive loop guard: each iteration either returns, breaks, or strictly advances
177+
// pageCursor by one position. The bound is therefore the page entry count; we use 2x
178+
// for safety in case an entry is legitimately skipped via two separate paths
179+
// (removedKeys and fromKeys non-inclusive).
180+
int safetyCounter = 0;
181+
final int safetyLimit = pageCursor != null ? Math.max(1024, pageCursor.totalKeys * 2) : 0;
176182
while (pageCursor != null) {
183+
if (++safetyCounter > safetyLimit)
184+
throw new IllegalStateException(
185+
"Detected infinite loop while initializing cursor on index '" + index.getName() + "' (DESC=" + (!ascendingOrder)
186+
+ ", iterations=" + safetyCounter + "). The index may be corrupted, please rebuild it.");
187+
177188
final TransactionIndexContext.ComparableKey keys = new TransactionIndexContext.ComparableKey(pageCursor.getKeys());
178189
if (removedKeys.contains(keys)) {
179190
if (pageCursor.hasNext()) {
@@ -281,7 +292,18 @@ public boolean hasNext() {
281292

282293
@Override
283294
public RID next() {
295+
// Defensive loop guard: a corrupted or buggy cursor should never iterate this body
296+
// more than a small multiple of (totalCursors + tx changes). If it does, we are
297+
// stuck and must surface the problem instead of hanging the thread; the index can
298+
// be rebuilt to recover.
299+
int safetyCounter = 0;
300+
final int safetyLimit = Math.max(1024, (totalCursors + 1) * 1024);
284301
do {
302+
if (++safetyCounter > safetyLimit)
303+
throw new IllegalStateException(
304+
"Detected infinite loop while iterating index '" + index.getName() + "' (DESC=" + (!ascendingOrder)
305+
+ ", iterations=" + safetyCounter + "). The index may be corrupted, please rebuild it.");
306+
285307
if (currentValues != null && currentValueIndex < currentValues.length) {
286308
final RID value = currentValues[currentValueIndex++];
287309
if (value != null && !index.isDeletedEntry(value))

‎engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexUnderlyingPageCursor.java‎

Lines changed: 49 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,49 @@ public Object[] getKeys() {
6464
if (currentEntryIndex < 0)
6565
throw new IllegalStateException("Invalid page cursor index " + currentEntryIndex);
6666

67-
int contentPos = buffer.getInt(keyStartPosition + (currentEntryIndex * INT_SERIALIZED_SIZE));
67+
int readPos = currentEntryIndex;
68+
69+
// For DESC iteration, scan backward to find the leftmost occurrence of the key at
70+
// currentEntryIndex. We then read from the leftmost and merge forward, so that:
71+
// 1. value insertion order is preserved (oldest first), keeping the deletion
72+
// semantics in LSMTreeIndexCursor.next() correct;
73+
// 2. after the merge, currentEntryIndex is reset to the leftmost position so that
74+
// the next call to next() skips past the entire duplicate group. Without this
75+
// reset, next() would decrement by 1 and re-enter the same merge group,
76+
// causing an infinite loop and returning duplicate entries.
77+
if (!ascendingOrder) {
78+
int currentContentPos = buffer.getInt(keyStartPosition + (currentEntryIndex * INT_SERIALIZED_SIZE));
79+
buffer.position(currentContentPos);
80+
final Object[] currentKey = new Object[keyTypes.length];
81+
for (int k = 0; k < keyTypes.length; ++k) {
82+
final boolean notNull = index.getVersion() < 1 || buffer.getByte() == 1;
83+
if (notNull)
84+
currentKey[k] = index.getDatabase().getSerializer().deserializeValue(index.getDatabase(), buffer, keyTypes[k], null);
85+
else
86+
currentKey[k] = null;
87+
}
88+
89+
for (int pos = currentEntryIndex - 1; pos >= 0; --pos) {
90+
final int prevContentPos = buffer.getInt(keyStartPosition + (pos * INT_SERIALIZED_SIZE));
91+
buffer.position(prevContentPos);
92+
93+
final Object[] adjacentKeys = new Object[keyTypes.length];
94+
for (int k = 0; k < keyTypes.length; ++k) {
95+
final boolean notNull = index.getVersion() < 1 || buffer.getByte() == 1;
96+
if (notNull)
97+
adjacentKeys[k] = index.getDatabase().getSerializer().deserializeValue(index.getDatabase(), buffer, keyTypes[k], null);
98+
else
99+
adjacentKeys[k] = null;
100+
}
101+
102+
if (LSMTreeIndexMutable.compareKeys(index.comparator, keyTypes, currentKey, adjacentKeys) != 0)
103+
break;
104+
105+
readPos = pos;
106+
}
107+
}
108+
109+
int contentPos = buffer.getInt(keyStartPosition + (readPos * INT_SERIALIZED_SIZE));
68110
buffer.position(contentPos);
69111

70112
nextKeys = new Object[keyTypes.length];
@@ -79,7 +121,9 @@ public Object[] getKeys() {
79121
valuePosition = buffer.position();
80122
nextValue = index.readEntryValues(buffer);
81123

82-
for (int pos = currentEntryIndex + 1; pos < totalKeys; ++pos) {
124+
final int leftmost = readPos;
125+
126+
for (int pos = readPos + 1; pos < totalKeys; ++pos) {
83127
contentPos = buffer.getInt(keyStartPosition + (pos * INT_SERIALIZED_SIZE));
84128
buffer.position(contentPos);
85129

@@ -110,6 +154,9 @@ public Object[] getKeys() {
110154
}
111155
}
112156

157+
if (!ascendingOrder)
158+
currentEntryIndex = leftmost;
159+
113160
return nextKeys;
114161
}
115162

‎engine/src/main/java/com/arcadedb/query/sql/executor/FetchFromIndexStep.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -133,7 +133,19 @@ public Result next() {
133133

134134
private void fetchNextEntry() {
135135
nextEntry = null;
136+
// Defensive loop guard: each iteration either returns, drops one element from
137+
// nextCursors, or toggles `cursor` between null and the next pending entry.
138+
// The bound is therefore proportional to the initial nextCursors size; a small
139+
// generous multiplier protects against any future cursor implementation that
140+
// misbehaves without depending on the underlying LSM/MultiIndex guards.
141+
int safetyCounter = 0;
142+
final int safetyLimit = (nextCursors.size() + 2) * 4;
136143
while (true) {
144+
if (++safetyCounter > safetyLimit)
145+
throw new IllegalStateException(
146+
"Detected infinite loop while fetching from index '" + indexName + "' (iterations=" + safetyCounter
147+
+ "). The index may be corrupted, please rebuild it.");
148+
137149
if (cursor == null) {
138150
if (nextCursors.isEmpty()) {
139151
if (nextEntry == null && customIterator != null && customIterator.hasNext()) {

0 commit comments

Comments
 (0)