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