Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: OpenGIS Simple Features Reference Implementation
4 : * Purpose: Implements management of FileGDB .freelist
5 : * Author: Even Rouault, <even dot rouault at spatialys.com>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2022, Even Rouault <even dot rouault at spatialys.com>
9 : *
10 : * SPDX-License-Identifier: MIT
11 : ****************************************************************************/
12 :
13 : #include "cpl_port.h"
14 :
15 : #include "filegdbtable.h"
16 : #include "filegdbtable_priv.h"
17 :
18 : #include <algorithm>
19 : #include <array>
20 : #include <cassert>
21 : #include <limits>
22 : #include <set>
23 :
24 : #include "cpl_string.h"
25 :
26 : namespace OpenFileGDB
27 : {
28 :
29 : constexpr uint32_t MINUS_ONE = 0xFFFFFFFFU;
30 :
31 : constexpr int MINIMUM_SIZE_FOR_FREELIST = 8;
32 :
33 : constexpr int nTrailerSize = 344;
34 : constexpr int nTrailerEntrySize = 2 * static_cast<int>(sizeof(uint32_t));
35 :
36 : constexpr int nPageSize = 4096;
37 : constexpr int nPageHeaderSize = 2 * static_cast<int>(sizeof(uint32_t));
38 :
39 : /************************************************************************/
40 : /* FindFreelistRangeSlot() */
41 : /************************************************************************/
42 :
43 : struct FreelistSlot
44 : {
45 : int nIdx;
46 : uint32_t nThisSize;
47 : uint32_t nNextSize;
48 : };
49 :
50 : // Fibonacci suite
51 : static const std::array<uint32_t, 43> anHoleSizes = {
52 : 0, 8, 16, 24, 40, 64,
53 : 104, 168, 272, 440, 712, 1152,
54 : 1864, 3016, 4880, 7896, 12776, 20672,
55 : 33448, 54120, 87568, 141688, 229256, 370944,
56 : 600200, 971144, 1571344, 2542488, 4113832, 6656320,
57 : 10770152, 17426472, 28196624, 45623096, 73819720, 119442816,
58 : 193262536, 312705352, 505967888, 818673240, 1324641128, 2143314368,
59 : 3467955496U};
60 :
61 5310 : static FreelistSlot FindFreelistRangeSlot(uint32_t nSize)
62 : {
63 55103 : for (size_t i = 0; i < anHoleSizes.size() - 1; i++)
64 : {
65 55103 : if (/* nSize >= anHoleSizes[i] && */ nSize < anHoleSizes[i + 1])
66 : {
67 : FreelistSlot slot;
68 5310 : slot.nIdx = static_cast<int>(i);
69 5310 : slot.nThisSize = anHoleSizes[i];
70 5310 : slot.nNextSize = anHoleSizes[i + 1];
71 5310 : return slot;
72 : }
73 : }
74 :
75 0 : CPLDebug("OpenFileGDB", "Hole larger than %u can be handled",
76 0 : anHoleSizes.back());
77 : FreelistSlot slot;
78 0 : slot.nIdx = -1;
79 0 : slot.nThisSize = 0;
80 0 : slot.nNextSize = 0;
81 0 : return slot;
82 : }
83 :
84 : /************************************************************************/
85 : /* AddEntryToFreelist() */
86 : /************************************************************************/
87 :
88 2676 : void FileGDBTable::AddEntryToFreelist(uint64_t nOffset, uint32_t nSize)
89 : {
90 2676 : if (nSize < MINIMUM_SIZE_FOR_FREELIST)
91 2 : return;
92 :
93 : const std::string osFilename =
94 2674 : CPLResetExtensionSafe(m_osFilename.c_str(), "freelist");
95 2674 : VSILFILE *fp = VSIFOpenL(osFilename.c_str(), "rb+");
96 2674 : if (fp == nullptr)
97 : {
98 : // Initialize an empty .freelist file
99 43 : fp = VSIFOpenL(osFilename.c_str(), "wb+");
100 43 : if (fp == nullptr)
101 0 : return;
102 43 : std::vector<GByte> abyTrailer;
103 43 : WriteUInt32(abyTrailer, 1);
104 43 : WriteUInt32(abyTrailer, MINUS_ONE);
105 1849 : for (int i = 0;
106 1849 : i < (nTrailerSize - nTrailerEntrySize) / nTrailerEntrySize; i++)
107 : {
108 1806 : WriteUInt32(abyTrailer, MINUS_ONE);
109 1806 : WriteUInt32(abyTrailer, 0);
110 : }
111 43 : CPLAssert(static_cast<int>(abyTrailer.size()) == nTrailerSize);
112 43 : if (VSIFWriteL(abyTrailer.data(), abyTrailer.size(), 1, fp) != 1)
113 : {
114 0 : VSIFCloseL(fp);
115 0 : return;
116 : }
117 : }
118 :
119 2674 : m_nHasFreeList = true;
120 :
121 : // Read trailer
122 2674 : VSIFSeekL(fp, 0, SEEK_END);
123 2674 : auto nFileSize = VSIFTellL(fp);
124 2674 : if ((nFileSize % nPageSize) != nTrailerSize)
125 : {
126 0 : VSIFCloseL(fp);
127 0 : return;
128 : }
129 :
130 2674 : VSIFSeekL(fp, nFileSize - nTrailerSize, SEEK_SET);
131 2674 : std::vector<GByte> abyTrailer(nTrailerSize);
132 2674 : if (VSIFReadL(abyTrailer.data(), abyTrailer.size(), 1, fp) != 1)
133 : {
134 0 : VSIFCloseL(fp);
135 0 : return;
136 : }
137 :
138 : // Determine in which "slot" of hole size the new entry belongs to
139 2674 : auto sSlot = FindFreelistRangeSlot(nSize);
140 2674 : if (sSlot.nIdx < 0)
141 : {
142 0 : VSIFCloseL(fp);
143 0 : return;
144 : }
145 2674 : assert(sSlot.nIdx < 100);
146 :
147 : // Read the last page index of the identified slot
148 : uint32_t nPageIdx =
149 2674 : GetUInt32(abyTrailer.data() + nTrailerEntrySize * sSlot.nIdx, 0);
150 : uint32_t nPageCount;
151 :
152 2674 : std::vector<GByte> abyPage;
153 2674 : bool bRewriteTrailer = false;
154 :
155 2674 : const int nEntrySize =
156 2674 : static_cast<int>(sizeof(uint32_t)) + m_nTablxOffsetSize;
157 2674 : const int nMaxEntriesPerPage = (nPageSize - nPageHeaderSize) / nEntrySize;
158 2674 : int nNumEntries = 0;
159 :
160 2674 : if (nPageIdx == MINUS_ONE)
161 : {
162 : // There's no allocate page for that range
163 : // So allocate one.
164 :
165 68 : WriteUInt32(abyPage, nNumEntries);
166 68 : WriteUInt32(abyPage, MINUS_ONE);
167 68 : abyPage.resize(nPageSize);
168 :
169 : // Update trailer
170 68 : bRewriteTrailer = true;
171 68 : nPageIdx =
172 68 : static_cast<uint32_t>((nFileSize - nTrailerSize) / nPageSize);
173 68 : nPageCount = 1;
174 :
175 68 : nFileSize += nPageSize; // virtual extension
176 : }
177 : else
178 : {
179 : nPageCount =
180 2606 : GetUInt32(abyTrailer.data() + nTrailerEntrySize * sSlot.nIdx +
181 : sizeof(uint32_t),
182 : 0);
183 :
184 2606 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
185 2606 : abyPage.resize(nPageSize);
186 2606 : if (VSIFReadL(abyPage.data(), abyPage.size(), 1, fp) != 1)
187 : {
188 0 : VSIFCloseL(fp);
189 0 : return;
190 : }
191 :
192 2606 : nNumEntries = GetUInt32(abyPage.data(), 0);
193 2606 : if (nNumEntries >= nMaxEntriesPerPage)
194 : {
195 : // Allocate new page
196 3 : abyPage.clear();
197 3 : nNumEntries = 0;
198 3 : WriteUInt32(abyPage, nNumEntries);
199 3 : WriteUInt32(abyPage, nPageIdx); // Link to previous page
200 3 : abyPage.resize(nPageSize);
201 :
202 : // Update trailer
203 3 : bRewriteTrailer = true;
204 3 : nPageIdx =
205 3 : static_cast<uint32_t>((nFileSize - nTrailerSize) / nPageSize);
206 3 : nPageCount++;
207 :
208 3 : nFileSize += nPageSize; // virtual extension
209 : }
210 : }
211 :
212 : // Add new entry into page
213 2674 : WriteUInt32(abyPage, nSize, nPageHeaderSize + nNumEntries * nEntrySize);
214 2674 : WriteFeatureOffset(nOffset, abyPage.data() + nPageHeaderSize +
215 2674 : nNumEntries * nEntrySize +
216 : sizeof(uint32_t));
217 :
218 : // Update page header
219 2674 : ++nNumEntries;
220 2674 : WriteUInt32(abyPage, nNumEntries, 0);
221 :
222 : // Flush page
223 2674 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
224 2674 : if (VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp) != 1)
225 : {
226 0 : VSIFCloseL(fp);
227 0 : return;
228 : }
229 :
230 2674 : if (bRewriteTrailer)
231 : {
232 71 : WriteUInt32(abyTrailer, nPageIdx, nTrailerEntrySize * sSlot.nIdx);
233 71 : WriteUInt32(abyTrailer, nPageCount,
234 71 : nTrailerEntrySize * sSlot.nIdx + sizeof(uint32_t));
235 :
236 71 : VSIFSeekL(fp, nFileSize - nTrailerSize, 0);
237 71 : if (VSIFWriteL(abyTrailer.data(), abyTrailer.size(), 1, fp) != 1)
238 : {
239 0 : VSIFCloseL(fp);
240 0 : return;
241 : }
242 : }
243 :
244 2674 : m_bFreelistCanBeDeleted = false;
245 :
246 2674 : VSIFCloseL(fp);
247 : }
248 :
249 : /************************************************************************/
250 : /* GetOffsetOfFreeAreaFromFreeList() */
251 : /************************************************************************/
252 :
253 33530 : uint64_t FileGDBTable::GetOffsetOfFreeAreaFromFreeList(uint32_t nSize)
254 : {
255 33530 : if (nSize < MINIMUM_SIZE_FOR_FREELIST || m_nHasFreeList == FALSE ||
256 5569 : m_bFreelistCanBeDeleted)
257 27964 : return OFFSET_MINUS_ONE;
258 :
259 : const std::string osFilename =
260 11132 : CPLResetExtensionSafe(m_osFilename.c_str(), "freelist");
261 5566 : VSILFILE *fp = VSIFOpenL(osFilename.c_str(), "rb+");
262 5566 : m_nHasFreeList = fp != nullptr;
263 5566 : if (fp == nullptr)
264 2930 : return OFFSET_MINUS_ONE;
265 :
266 : // Read trailer
267 2636 : VSIFSeekL(fp, 0, SEEK_END);
268 2636 : auto nFileSize = VSIFTellL(fp);
269 :
270 2636 : if ((nFileSize % nPageSize) != nTrailerSize)
271 : {
272 0 : VSIFCloseL(fp);
273 0 : return OFFSET_MINUS_ONE;
274 : }
275 :
276 2636 : VSIFSeekL(fp, nFileSize - nTrailerSize, SEEK_SET);
277 5272 : std::vector<GByte> abyTrailer(nTrailerSize);
278 2636 : if (VSIFReadL(abyTrailer.data(), abyTrailer.size(), 1, fp) != 1)
279 : {
280 0 : VSIFCloseL(fp);
281 0 : return OFFSET_MINUS_ONE;
282 : }
283 :
284 : // Determine in which "slot" of hole size the new entry belongs to
285 2636 : const auto sSlot = FindFreelistRangeSlot(nSize);
286 2636 : if (sSlot.nIdx < 0)
287 : {
288 0 : VSIFCloseL(fp);
289 0 : return OFFSET_MINUS_ONE;
290 : }
291 2636 : assert(sSlot.nIdx < 100);
292 :
293 : // Read the last page index of the identified slot
294 : uint32_t nPageIdx =
295 2636 : GetUInt32(abyTrailer.data() + nTrailerEntrySize * sSlot.nIdx, 0);
296 2636 : if (nPageIdx == MINUS_ONE)
297 : {
298 10 : VSIFCloseL(fp);
299 10 : return OFFSET_MINUS_ONE;
300 : }
301 :
302 2626 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
303 5252 : std::vector<GByte> abyPage(nPageSize);
304 2626 : if (VSIFReadL(abyPage.data(), abyPage.size(), 1, fp) != 1)
305 : {
306 0 : CPLDebug("OpenFileGDB", "Can't read freelist page %u", nPageIdx);
307 0 : VSIFCloseL(fp);
308 0 : return OFFSET_MINUS_ONE;
309 : }
310 :
311 2626 : const int nEntrySize =
312 2626 : static_cast<int>(sizeof(uint32_t)) + m_nTablxOffsetSize;
313 2626 : const int nMaxEntriesPerPage = (nPageSize - nPageHeaderSize) / nEntrySize;
314 :
315 : // Index of page that links to us
316 2626 : uint32_t nReferencingPage = MINUS_ONE;
317 5252 : std::vector<GByte> abyReferencingPage;
318 :
319 2626 : int nBestCandidateNumEntries = 0;
320 2626 : uint32_t nBestCandidatePageIdx = MINUS_ONE;
321 2626 : uint32_t nBestCandidateSize = std::numeric_limits<uint32_t>::max();
322 2626 : int iBestCandidateEntry = -1;
323 2626 : uint32_t nBestCandidateReferencingPage = MINUS_ONE;
324 5252 : std::vector<GByte> abyBestCandidateReferencingPage;
325 5252 : std::vector<GByte> abyBestCandidatePage;
326 :
327 7878 : std::set<uint32_t> aSetReadPages = {nPageIdx};
328 : while (true)
329 : {
330 : int nNumEntries = static_cast<int>(
331 3534 : std::min(GetUInt32(abyPage.data(), 0),
332 7068 : static_cast<uint32_t>(nMaxEntriesPerPage)));
333 3534 : bool bExactMatch = false;
334 335391 : for (int i = nNumEntries - 1; i >= 0; i--)
335 : {
336 : const uint32_t nFreeAreaSize =
337 334471 : GetUInt32(abyPage.data() + nPageHeaderSize + i * nEntrySize, 0);
338 334471 : if (nFreeAreaSize < sSlot.nThisSize ||
339 334471 : nFreeAreaSize >= sSlot.nNextSize)
340 : {
341 0 : CPLError(CE_Warning, CPLE_AppDefined,
342 : "Page %u of %s contains free area of unexpected size "
343 : "at entry %d",
344 : nPageIdx, osFilename.c_str(), i);
345 : }
346 334471 : else if (nFreeAreaSize == nSize ||
347 6235 : (nFreeAreaSize > nSize &&
348 : nFreeAreaSize < nBestCandidateSize))
349 : {
350 4366 : if (nBestCandidatePageIdx != nPageIdx)
351 : {
352 2616 : abyBestCandidatePage = abyPage;
353 2616 : abyBestCandidateReferencingPage = abyReferencingPage;
354 : }
355 4366 : nBestCandidatePageIdx = nPageIdx;
356 4366 : nBestCandidateReferencingPage = nReferencingPage;
357 4366 : iBestCandidateEntry = i;
358 4366 : nBestCandidateSize = nFreeAreaSize;
359 4366 : nBestCandidateNumEntries = nNumEntries;
360 4366 : if (nFreeAreaSize == nSize)
361 : {
362 2614 : bExactMatch = true;
363 2614 : break;
364 : }
365 : }
366 : }
367 :
368 3534 : if (!bExactMatch)
369 : {
370 : const uint32_t nPrevPage =
371 920 : GetUInt32(abyPage.data() + sizeof(uint32_t), 0);
372 920 : if (nPrevPage == MINUS_ONE)
373 : {
374 12 : break;
375 : }
376 :
377 908 : if (cpl::contains(aSetReadPages, nPrevPage))
378 : {
379 0 : CPLError(CE_Warning, CPLE_AppDefined,
380 : "Cyclic page refererencing in %s", osFilename.c_str());
381 0 : VSIFCloseL(fp);
382 0 : return OFFSET_MINUS_ONE;
383 : }
384 908 : aSetReadPages.insert(nPrevPage);
385 :
386 908 : abyReferencingPage = abyPage;
387 908 : nReferencingPage = nPageIdx;
388 908 : nPageIdx = nPrevPage;
389 908 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
390 908 : if (VSIFReadL(abyPage.data(), abyPage.size(), 1, fp) != 1)
391 : {
392 0 : CPLDebug("OpenFileGDB", "Can't read freelist page %u",
393 : nPageIdx);
394 0 : break;
395 : }
396 : }
397 : else
398 : {
399 2614 : break;
400 : }
401 908 : }
402 :
403 2626 : if (nBestCandidatePageIdx == MINUS_ONE)
404 : {
405 : // If we go here, it means that the trailer section references empty
406 : // pages or pages with features of unexpected size.
407 : // Shouldn't happen for well-behaved .freelist files
408 10 : VSIFCloseL(fp);
409 10 : return OFFSET_MINUS_ONE;
410 : }
411 :
412 2616 : nPageIdx = nBestCandidatePageIdx;
413 2616 : nReferencingPage = nBestCandidateReferencingPage;
414 2616 : abyPage = std::move(abyBestCandidatePage);
415 2616 : abyReferencingPage = std::move(abyBestCandidateReferencingPage);
416 :
417 : uint64_t nCandidateOffset =
418 2616 : ReadFeatureOffset(abyPage.data() + nPageHeaderSize +
419 2616 : iBestCandidateEntry * nEntrySize + sizeof(uint32_t));
420 :
421 : // Remove entry from page
422 2616 : if (iBestCandidateEntry < nBestCandidateNumEntries - 1)
423 : {
424 4752 : memmove(abyPage.data() + nPageHeaderSize +
425 1584 : iBestCandidateEntry * nEntrySize,
426 1584 : abyPage.data() + nPageHeaderSize +
427 1584 : (iBestCandidateEntry + 1) * nEntrySize,
428 1584 : cpl::fits_on<int>(
429 1584 : (nBestCandidateNumEntries - 1 - iBestCandidateEntry) *
430 : nEntrySize));
431 : }
432 2616 : memset(abyPage.data() + nPageHeaderSize +
433 2616 : (nBestCandidateNumEntries - 1) * nEntrySize,
434 : 0, nEntrySize);
435 :
436 2616 : nBestCandidateNumEntries--;
437 2616 : WriteUInt32(abyPage, nBestCandidateNumEntries, 0);
438 :
439 2616 : if (nBestCandidateNumEntries > 0)
440 : {
441 : // Rewrite updated page
442 2588 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
443 2588 : CPL_IGNORE_RET_VAL(VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp));
444 : }
445 : else
446 : {
447 : const uint32_t nPrevPage =
448 28 : GetUInt32(abyPage.data() + sizeof(uint32_t), 0);
449 :
450 : // Link this newly free page to the previous one
451 : const uint32_t nLastFreePage =
452 28 : GetUInt32(abyTrailer.data() + sizeof(uint32_t), 0);
453 28 : WriteUInt32(abyPage, nLastFreePage, sizeof(uint32_t));
454 :
455 : // Rewrite updated page
456 28 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
457 28 : CPL_IGNORE_RET_VAL(VSIFWriteL(abyPage.data(), abyPage.size(), 1, fp));
458 :
459 : // Update trailer to add a new free page
460 28 : WriteUInt32(abyTrailer, nPageIdx, sizeof(uint32_t));
461 :
462 28 : if (nReferencingPage != MINUS_ONE)
463 : {
464 : // Links referencing page to previous page
465 0 : WriteUInt32(abyReferencingPage, nPrevPage, sizeof(uint32_t));
466 0 : VSIFSeekL(fp, static_cast<uint64_t>(nReferencingPage) * nPageSize,
467 : 0);
468 0 : CPL_IGNORE_RET_VAL(VSIFWriteL(abyReferencingPage.data(),
469 : abyReferencingPage.size(), 1, fp));
470 : }
471 : else
472 : {
473 : // and make the slot points to the previous page
474 28 : WriteUInt32(abyTrailer, nPrevPage, nTrailerEntrySize * sSlot.nIdx);
475 : }
476 :
477 : uint32_t nPageCount =
478 28 : GetUInt32(abyTrailer.data() + nTrailerEntrySize * sSlot.nIdx +
479 : sizeof(uint32_t),
480 : 0);
481 28 : if (nPageCount == 0)
482 : {
483 0 : CPLDebug("OpenFileGDB", "Wrong page count for %s at slot %d",
484 0 : osFilename.c_str(), sSlot.nIdx);
485 : }
486 : else
487 : {
488 28 : nPageCount--;
489 28 : WriteUInt32(abyTrailer, nPageCount,
490 28 : nTrailerEntrySize * sSlot.nIdx + sizeof(uint32_t));
491 28 : if (nPageCount == 0)
492 : {
493 : // Check if the freelist no longer contains pages with free
494 : // slots
495 25 : m_bFreelistCanBeDeleted = true;
496 333 : for (int i = 1; i < nTrailerSize / nTrailerEntrySize; i++)
497 : {
498 326 : if (GetUInt32(abyTrailer.data() + i * nTrailerEntrySize +
499 : sizeof(uint32_t),
500 326 : 0) != 0)
501 : {
502 18 : m_bFreelistCanBeDeleted = false;
503 18 : break;
504 : }
505 : }
506 : }
507 : }
508 :
509 28 : VSIFSeekL(fp, nFileSize - nTrailerSize, 0);
510 28 : CPL_IGNORE_RET_VAL(
511 28 : VSIFWriteL(abyTrailer.data(), abyTrailer.size(), 1, fp));
512 : }
513 :
514 : // Extra precaution: check that the uint32_t at offset nOffset is a
515 : // negated compatible size
516 2616 : auto nOffset = nCandidateOffset;
517 2616 : VSIFSeekL(m_fpTable, nOffset, 0);
518 2616 : uint32_t nOldSize = 0;
519 2616 : if (!ReadUInt32(m_fpTable, nOldSize) || (nOldSize >> 31) == 0)
520 : {
521 0 : nOffset = OFFSET_MINUS_ONE;
522 : }
523 : else
524 : {
525 2616 : nOldSize = static_cast<uint32_t>(-static_cast<int>(nOldSize));
526 2616 : if (nOldSize < nSize - sizeof(uint32_t))
527 : {
528 0 : nOffset = OFFSET_MINUS_ONE;
529 : }
530 : }
531 2616 : if (nOffset == OFFSET_MINUS_ONE)
532 : {
533 0 : CPLDebug("OpenFileGDB",
534 : "%s references a free area at offset " CPL_FRMT_GUIB
535 : ", but it does not appear to match a deleted "
536 : "feature",
537 : osFilename.c_str(), static_cast<GUIntBig>(nCandidateOffset));
538 : }
539 :
540 2616 : VSIFCloseL(fp);
541 2616 : return nOffset;
542 : }
543 :
544 : /************************************************************************/
545 : /* CheckFreeListConsistency() */
546 : /************************************************************************/
547 :
548 8 : bool FileGDBTable::CheckFreeListConsistency()
549 : {
550 : const std::string osFilename =
551 16 : CPLResetExtensionSafe(m_osFilename.c_str(), "freelist");
552 8 : VSILFILE *fp = VSIFOpenL(osFilename.c_str(), "rb");
553 8 : if (fp == nullptr)
554 0 : return true;
555 :
556 : // Read trailer
557 8 : VSIFSeekL(fp, 0, SEEK_END);
558 8 : auto nFileSize = VSIFTellL(fp);
559 :
560 8 : if ((nFileSize % nPageSize) != nTrailerSize)
561 : {
562 0 : CPLError(CE_Failure, CPLE_AppDefined, "Bad file size");
563 0 : VSIFCloseL(fp);
564 0 : return false;
565 : }
566 :
567 8 : VSIFSeekL(fp, nFileSize - nTrailerSize, SEEK_SET);
568 16 : std::vector<GByte> abyTrailer(nTrailerSize);
569 8 : if (VSIFReadL(abyTrailer.data(), abyTrailer.size(), 1, fp) != 1)
570 : {
571 0 : CPLError(CE_Failure, CPLE_AppDefined, "Cannot read trailer section");
572 0 : VSIFCloseL(fp);
573 0 : return false;
574 : }
575 :
576 8 : if (GetUInt32(abyTrailer.data(), 0) != 1)
577 : {
578 0 : CPLError(CE_Failure, CPLE_AppDefined,
579 : "Unexpected value for first uint32 of trailer section");
580 0 : VSIFCloseL(fp);
581 0 : return false;
582 : }
583 :
584 16 : std::vector<GByte> abyPage(nPageSize);
585 16 : std::set<uint32_t> setVisitedPages;
586 :
587 : // Check free pages
588 8 : uint32_t nFreePage = GetUInt32(abyTrailer.data() + sizeof(uint32_t), 0);
589 34 : while (nFreePage != MINUS_ONE)
590 : {
591 26 : if (cpl::contains(setVisitedPages, nFreePage))
592 : {
593 0 : CPLError(CE_Failure, CPLE_AppDefined,
594 : "Cyclic page refererencing in free pages");
595 0 : VSIFCloseL(fp);
596 0 : return false;
597 : }
598 :
599 26 : VSIFSeekL(fp, static_cast<uint64_t>(nFreePage) * nPageSize, 0);
600 26 : if (VSIFReadL(abyPage.data(), abyPage.size(), 1, fp) != 1)
601 : {
602 0 : CPLError(CE_Failure, CPLE_AppDefined, "Can't read freelist page %u",
603 : nFreePage);
604 0 : VSIFCloseL(fp);
605 0 : return false;
606 : }
607 :
608 26 : setVisitedPages.insert(nFreePage);
609 :
610 26 : if (GetUInt32(abyPage.data(), 0) != 0)
611 : {
612 0 : CPLError(CE_Failure, CPLE_AppDefined,
613 : "Unexpected value for first uint32 of free page");
614 0 : VSIFCloseL(fp);
615 0 : return false;
616 : }
617 :
618 26 : nFreePage = GetUInt32(abyPage.data() + sizeof(uint32_t), 0);
619 : }
620 :
621 : // Check active pages
622 8 : const int nEntrySize =
623 8 : static_cast<int>(sizeof(uint32_t)) + m_nTablxOffsetSize;
624 8 : const int nMaxEntriesPerPage = (nPageSize - nPageHeaderSize) / nEntrySize;
625 :
626 16 : std::set<uint64_t> aSetOffsets;
627 :
628 344 : for (int iSlot = 1; iSlot < (nTrailerSize / nTrailerEntrySize); iSlot++)
629 : {
630 : uint32_t nPageIdx =
631 336 : GetUInt32(abyTrailer.data() + iSlot * nTrailerEntrySize, 0);
632 336 : uint32_t nActualCount = 0;
633 361 : while (nPageIdx != MINUS_ONE)
634 : {
635 25 : if (cpl::contains(setVisitedPages, nPageIdx))
636 : {
637 0 : CPLError(CE_Failure, CPLE_AppDefined,
638 : "Cyclic page refererencing or page referenced more "
639 : "than once");
640 0 : VSIFCloseL(fp);
641 0 : return false;
642 : }
643 :
644 25 : VSIFSeekL(fp, static_cast<uint64_t>(nPageIdx) * nPageSize, 0);
645 25 : if (VSIFReadL(abyPage.data(), abyPage.size(), 1, fp) != 1)
646 : {
647 0 : CPLError(CE_Failure, CPLE_AppDefined,
648 : "Can't read active page %u", nPageIdx);
649 0 : VSIFCloseL(fp);
650 0 : return false;
651 : }
652 :
653 25 : setVisitedPages.insert(nPageIdx);
654 25 : nActualCount++;
655 :
656 25 : const uint32_t nEntries = GetUInt32(abyPage.data(), 0);
657 25 : if (nEntries == 0 ||
658 25 : nEntries > static_cast<uint32_t>(nMaxEntriesPerPage))
659 : {
660 0 : CPLError(
661 : CE_Failure, CPLE_AppDefined,
662 : "Unexpected value for entries count of active page %u: %d",
663 : nPageIdx, nEntries);
664 0 : VSIFCloseL(fp);
665 0 : return false;
666 : }
667 :
668 2628 : for (uint32_t i = 0; i < nEntries; ++i)
669 : {
670 2603 : const uint32_t nFreeAreaSize = GetUInt32(
671 2603 : abyPage.data() + nPageHeaderSize + i * nEntrySize, 0);
672 2603 : assert(iSlot >= 0);
673 2603 : assert(iSlot + 1 < static_cast<int>(anHoleSizes.size()));
674 5206 : if (nFreeAreaSize < anHoleSizes[iSlot] ||
675 2603 : nFreeAreaSize >= anHoleSizes[iSlot + 1])
676 : {
677 0 : CPLError(CE_Failure, CPLE_AppDefined,
678 : "Page %u contains free area of unexpected size at "
679 : "entry %u",
680 : nPageIdx, i);
681 0 : VSIFCloseL(fp);
682 0 : return false;
683 : }
684 :
685 : const uint64_t nOffset =
686 2603 : ReadFeatureOffset(abyPage.data() + nPageHeaderSize +
687 2603 : i * nEntrySize + sizeof(uint32_t));
688 :
689 2603 : VSIFSeekL(m_fpTable, nOffset, 0);
690 2603 : uint32_t nOldSize = 0;
691 2603 : if (!ReadUInt32(m_fpTable, nOldSize))
692 : {
693 0 : CPLError(CE_Failure, CPLE_AppDefined,
694 : "Page %u contains free area that points to "
695 : "invalid offset " CPL_FRMT_GUIB,
696 : nPageIdx, static_cast<GUIntBig>(nOffset));
697 0 : VSIFCloseL(fp);
698 0 : return false;
699 : }
700 5206 : if ((nOldSize >> 31) == 0 ||
701 2603 : (nOldSize = static_cast<uint32_t>(-static_cast<int>(
702 2603 : nOldSize))) != nFreeAreaSize - sizeof(uint32_t))
703 : {
704 0 : CPLError(CE_Failure, CPLE_AppDefined,
705 : "Page %u contains free area that points to dead "
706 : "zone at offset " CPL_FRMT_GUIB
707 : " of unexpected size: %u",
708 : nPageIdx, static_cast<GUIntBig>(nOffset),
709 : nOldSize);
710 0 : VSIFCloseL(fp);
711 0 : return false;
712 : }
713 :
714 2603 : if (cpl::contains(aSetOffsets, nOffset))
715 : {
716 0 : CPLError(CE_Failure, CPLE_AppDefined,
717 : "Page %u contains free area that points to "
718 : "offset " CPL_FRMT_GUIB " already referenced",
719 : nPageIdx, static_cast<GUIntBig>(nOffset));
720 0 : VSIFCloseL(fp);
721 0 : return false;
722 : }
723 2603 : aSetOffsets.insert(nOffset);
724 : }
725 :
726 25 : nPageIdx = GetUInt32(abyPage.data() + sizeof(uint32_t), 0);
727 : }
728 :
729 336 : const uint32_t nPageCount = GetUInt32(
730 336 : abyTrailer.data() + iSlot * nTrailerEntrySize + sizeof(uint32_t),
731 : 0);
732 336 : if (nPageCount != nActualCount)
733 : {
734 0 : CPLError(CE_Failure, CPLE_AppDefined,
735 : "Unexpected value for page count of slot %d: %u vs %u",
736 : iSlot, nPageCount, nActualCount);
737 0 : VSIFCloseL(fp);
738 0 : return false;
739 : }
740 : }
741 :
742 8 : const auto nExpectedPageCount = (nFileSize - nTrailerSize) / nPageSize;
743 8 : if (setVisitedPages.size() != nExpectedPageCount)
744 : {
745 0 : CPLError(CE_Failure, CPLE_AppDefined,
746 : "%u pages have been visited, but there are %u pages in total",
747 0 : static_cast<uint32_t>(setVisitedPages.size()),
748 : static_cast<uint32_t>(nExpectedPageCount));
749 0 : VSIFCloseL(fp);
750 0 : return false;
751 : }
752 :
753 8 : VSIFCloseL(fp);
754 8 : return true;
755 : }
756 :
757 : /************************************************************************/
758 : /* DeleteFreeList() */
759 : /************************************************************************/
760 :
761 45 : void FileGDBTable::DeleteFreeList()
762 : {
763 45 : m_bFreelistCanBeDeleted = false;
764 45 : m_nHasFreeList = -1;
765 45 : VSIUnlink(CPLResetExtensionSafe(m_osFilename.c_str(), "freelist").c_str());
766 45 : }
767 :
768 : } /* namespace OpenFileGDB */
|
