1
#include "facet-tree-index.h"
2
 
3
#include <kj/debug.h>
4
#include <kj/io.h>
5
 
6
namespace workerd::server {
7
 
8
using kj::byte;
9
using kj::uint;
10
 
11
FacetTreeIndex::FacetTreeIndex(kj::Own<const kj::File> fileParam): file(kj::mv(fileParam)) {
12
  // Read the file to populate the initial index
13
 
14
  auto fileBytes = file->readAllBytes();
15
 
16
  // Check if the magic number is present.
17
  //
18
  // If the file size is less than or equal to the magic number size itself, it's possible that a
19
  // previous session suffered a failure while writing the magic number. In that case we can assume
20
  // nothing was ever written to the index, so we just rewrite it and start over.
21
  if (fileBytes.size() <= sizeof(MAGIC_NUMBER)) {
22
    // New file, initialize with magic number.
23
    file->write(0, kj::asBytes(MAGIC_NUMBER));
24
    file->datasync();
25
    offset = sizeof(MAGIC_NUMBER);
26
    return;
27
  }
28
 
29
  // On the other hand, because we datasync() immediately after writing the magic number, we can
30
  // assume that if _more_ bytes are written than just the magic number, then a failure did _not_
31
  // occurr during the writing of the magic number, and therefore, if it contains the wrong bytes,
32
  // the file must be in a format we don't recognize.
33
  uint64_t magic = 0;
34
  memcpy(&magic, fileBytes.begin(), sizeof(magic));
35
  KJ_REQUIRE(magic == MAGIC_NUMBER, "unknown magic number on facet tree index");
36
  offset = sizeof(magic);
37
 
38
  // Read entries
39
  while (offset + sizeof(EntryHeader) <= fileBytes.size()) {
40
    KJ_REQUIRE(nextId() <= MAX_ID, "Maximum number of facets exceeded");
41
 
42
    EntryHeader header;
43
    memcpy(&header, fileBytes.begin() + offset, sizeof(header));
44
 
45
    // Validation checks
46
    if (header.nameLength == 0) {
47
      // Empty name is invalid.
48
      break;
49
    }
50
 
51
    if (offset + sizeof(EntryHeader) + header.nameLength > fileBytes.size()) {
52
      // Name extends beyond file bounds, invalid.
53
      break;
54
    }
55
 
56
    if (header.parentId >= nextId()) {
57
      // Invalid parent ID (parent must already exist).
58
      break;
59
    }
60
 
61
    // Extract the name
62
    kj::String name = kj::heapString(
63
        reinterpret_cast<const char*>(fileBytes.begin() + offset + sizeof(EntryHeader)),
64
        header.nameLength);
65
 
66
    bool duplicate = false;
67
    entries.upsert(
68
        Entry{header.parentId, kj::mv(name)}, [&](Entry&, Entry&&) { duplicate = true; });
69
 
70
    if (duplicate) {
71
      // Duplicate entry is invalid.
72
      break;
73
    }
74
 
75
    // Entry was valid and processed successfully, now we can update the offset
76
    offset += sizeof(EntryHeader) + header.nameLength;
77
  }
78
 
79
  if (offset < fileBytes.size()) {
80
    // It appears we stopped at a corrupted entry. We assume such corruption can only be the result
81
    // of a power failure in the middle of writing an entry during a past session. Any entry which
82
    // was written but not synced can be presumed to have never been used, so we can simply
83
    // truncate it from the file.
84
    file->truncate(offset);
85
  }
86
}
87
 
88
uint FacetTreeIndex::getId(uint parent, kj::StringPtr name) {
89
  KJ_REQUIRE(name.size() > 0, "Facet name cannot be empty");
90
  KJ_REQUIRE(name.size() <= (uint16_t)kj::maxValue, "Facet name too long");
91
  KJ_REQUIRE(parent <= entries.size(), "Invalid parent ID");
92
 
93
  // Use findOrCreate to either find an existing entry or create a new one
94
  auto& entry = entries.findOrCreate(EntryPtr{parent, name}, [&]() -> Entry {
95
    // New entry, need to assign a new ID and append to file
96
    KJ_REQUIRE(nextId() <= MAX_ID, "Maximum number of facets exceeded");
97
 
98
    // Prepare entry data
99
    EntryHeader header{
100
      .parentId = static_cast<uint16_t>(parent),
101
      .nameLength = static_cast<uint16_t>(name.size()),
102
    };
103
 
104
// Don't whine about VLA being non-standard.
105
#pragma clang diagnostic ignored "-Wvla-cxx-extension"
106
 
107
    size_t entrySize = sizeof(EntryHeader) + header.nameLength;
108
    byte entryData[entrySize];
109
    memcpy(entryData, &header, sizeof(header));
110
    memcpy(entryData + sizeof(EntryHeader), name.begin(), header.nameLength);
111
 
112
    file->write(offset, kj::arrayPtr(entryData, entrySize));
113
 
114
    // We don't want to return an entry that might disappear after a power failure, so sync it
115
    // now.
116
    file->datasync();
117
 
118
    offset += entrySize;
119
 
120
    return Entry{parent, kj::heapString(name)};
121
  });
122
 
123
  // Calculate the ID based on the entry's position in the set
124
  // Root facet (ID 0) isn't in the entries set, so add 1 to the index
125
  return 1 + (&entry - entries.begin());
126
}
127
 
128
}  // namespace workerd::server