My Project 4.4.2
C++ Distributed Hash Table
Loading...
Searching...
No Matches
pht.h
1// Copyright (c) 2014-2026 Savoir-faire Linux Inc.
2// SPDX-License-Identifier: MIT
3#pragma once
4
5#include <string>
6#include <vector>
7#include <memory>
8#include <map>
9#include <functional>
10#include <stdexcept>
11#include <bitset>
12#include <iostream>
13#include <sstream>
14
15#include "../value.h"
16#include "../dhtrunner.h"
17#include "../infohash.h"
18
19namespace dht {
20namespace indexation {
21
31struct OPENDHT_PUBLIC Prefix
32{
33 Prefix() {}
34 Prefix(InfoHash h)
35 : size_(h.size() * 8)
36 , content_(h.begin(), h.end())
37 {}
38 Prefix(const Blob& d, const Blob& f = {})
39 : size_(d.size() * 8)
40 , flags_(f)
41 , content_(d)
42 {}
43
44 Prefix(const Prefix& p, size_t first)
45 : size_(std::min(first, p.content_.size() * 8))
46 , content_(Blob(p.content_.begin(), p.content_.begin() + size_ / 8))
47 {
48 auto rem = size_ % 8;
49 if (not p.flags_.empty()) {
50 flags_ = Blob(p.flags_.begin(), p.flags_.begin() + size_ / 8);
51 if (rem)
52 flags_.push_back(p.flags_[size_ / 8] & (0xFF << (8 - rem)));
53 }
54
55 if (rem)
56 content_.push_back(p.content_[size_ / 8] & (0xFF << (8 - rem)));
57 }
58
71 Prefix getPrefix(ssize_t len) const
72 {
73 if ((size_t) std::abs(len) >= content_.size() * 8)
74 throw std::out_of_range("len larger than prefix size.");
75 if (len < 0)
76 len += size_;
77
78 return Prefix(*this, len);
79 }
80
87 bool isFlagActive(size_t pos) const { return flags_.empty() or isActiveBit(flags_, pos); }
88
92 bool isContentBitActive(size_t pos) const { return isActiveBit(content_, pos); }
93
94 Prefix getFullSize() { return Prefix(*this, content_.size() * 8); }
95
101 Prefix getSibling() const
102 {
103 Prefix copy = *this;
104 if (size_)
105 copy.swapContentBit(size_ - 1);
106
107 return copy;
108 }
109
110 InfoHash hash() const
111 {
112 Blob copy(content_);
113 copy.push_back(size_);
114 return InfoHash::get(copy);
115 }
116
124 static inline unsigned commonBits(const Prefix& p1, const Prefix& p2)
125 {
126 /* size_ counts bits, so the comparison walks bits: reading it as a
127 byte count would run past the end of the shorter content. */
128 auto longest_prefix_size = std::min(p1.size_, p2.size_);
129
130 unsigned common = 0;
131 while (common < longest_prefix_size) {
132 if (not p1.isFlagActive(common) or not p2.isFlagActive(common)
133 or p1.isContentBitActive(common) != p2.isContentBitActive(common))
134 break;
135 common++;
136 }
137
138 return common;
139 }
140
144 void swapContentBit(size_t bit) { swapBit(content_, bit); }
145
149 void swapFlagBit(size_t bit) { swapBit(flags_, bit); }
150
154 void addPaddingContent(size_t size) { content_ = addPadding(content_, size); }
155
156 void updateFlags()
157 {
158 /* Fill first known bit */
159 auto csize = size_ - flags_.size() * 8;
160 while (csize >= 8) {
161 flags_.push_back(0xFF);
162 csize -= 8;
163 }
164
165 /* if needed fill remaining bit */
166 if (csize)
167 flags_.push_back(0xFF << (8 - csize));
168
169 /* Complet vector space missing */
170 for (auto i = flags_.size(); i < content_.size(); i++)
171 flags_.push_back(0xFF);
172 }
173
174 std::string toString() const;
175
176 size_t size_ {0};
177
178 /* Will contain flags according to content_.
179 If flags_[i] == 0, then content_[i] is unknown
180 else if flags_[i] == 1, then content_[i] is known */
181 Blob flags_ {};
182 Blob content_ {};
183
184private:
193 Blob addPadding(Blob toP, size_t size)
194 {
195 Blob copy = toP;
196 for (auto i = copy.size(); i < size; i++)
197 copy.push_back(0);
198
199 swapBit(copy, size_);
200 return copy;
201 }
202
213 bool isActiveBit(const Blob& b, size_t pos) const
214 {
215 if (pos >= content_.size() * 8)
216 throw std::out_of_range("Can't detect active bit at pos, pos larger than prefix size or empty prefix");
217
218 return ((b[pos / 8] >> (7 - (pos % 8))) & 1) == 1;
219 }
220
231 void swapBit(Blob& b, size_t bit)
232 {
233 if (bit >= b.size() * 8)
234 throw std::out_of_range("bit larger than prefix size.");
235
236 /* Bit 0 is the most significant one of the first byte, as
237 isActiveBit reads it. */
238 b[bit / 8] ^= (1 << (7 - (bit % 8)));
239 }
240};
241
242using Value = std::pair<InfoHash, dht::Value::Id>;
243struct OPENDHT_PUBLIC IndexEntry : public dht::Value::Serializable<IndexEntry>
244{
245 static const ValueType& TYPE;
246
247 virtual void unpackValue(const dht::Value& v)
248 {
249 Serializable<IndexEntry>::unpackValue(v);
250 name = v.user_type;
251 }
252
253 virtual dht::Value packValue() const
254 {
255 auto pack = Serializable<IndexEntry>::packValue();
256 pack.user_type = name;
257 return pack;
258 }
259
260 Blob prefix;
261 Value value;
262 std::string name;
263 MSGPACK_DEFINE_MAP(prefix, value)
264};
265
266class OPENDHT_PUBLIC Pht
267{
268 static constexpr const char* INVALID_KEY = "Key does not match the PHT key spec.";
269
270 /* Prefixes the user_type for all dht values put on the DHT */
271 static constexpr const char* INDEX_PREFIX = "index.pht.";
272
273public:
274 /* This is the maximum number of entries per node. This parameter is
275 * critical and influences the traffic a lot during a lookup operation.
276 */
277 static constexpr const size_t MAX_NODE_ENTRY_COUNT {16};
278
279 /* A key for a an index entry */
280 using Key = std::map<std::string, Blob>;
281
282 /* Specifications of the keys. It defines the number, the length and the
283 * serialization order of fields. */
284 using KeySpec = std::map<std::string, size_t>;
285 using LookupCallback = std::function<void(std::vector<std::shared_ptr<Value>>& values, const Prefix& p)>;
286
287 typedef void (*LookupCallbackRaw)(std::vector<std::shared_ptr<Value>>* values, Prefix* p, void* user_data);
288 static LookupCallback bindLookupCb(LookupCallbackRaw raw_cb, void* user_data)
289 {
290 if (not raw_cb)
291 return {};
292 return [=](std::vector<std::shared_ptr<Value>>& values, const Prefix& p) {
293 raw_cb((std::vector<std::shared_ptr<Value>>*) &values, (Prefix*) &p, user_data);
294 };
295 }
296 using LookupCallbackSimple = std::function<void(std::vector<std::shared_ptr<Value>>& values)>;
297 typedef void (*LookupCallbackSimpleRaw)(std::vector<std::shared_ptr<Value>>* values, void* user_data);
298 static LookupCallbackSimple bindLookupCbSimple(LookupCallbackSimpleRaw raw_cb, void* user_data)
299 {
300 if (not raw_cb)
301 return {};
302 return [=](std::vector<std::shared_ptr<Value>>& values) {
303 raw_cb((std::vector<std::shared_ptr<Value>>*) &values, user_data);
304 };
305 }
306
307 Pht(std::string name, KeySpec k_spec, std::shared_ptr<DhtRunner> dht)
308 : name_(INDEX_PREFIX + name)
309 , canary_(name_ + ".canary")
310 , keySpec_(k_spec)
311 , dht_(dht)
312 {}
313
314 virtual ~Pht() {}
315
319 void lookup(Key k, LookupCallback cb = {}, DoneCallbackSimple done_cb = {}, bool exact_match = true);
320 void lookup(Key k, LookupCallbackSimple cb = {}, DoneCallbackSimple done_cb = {}, bool exact_match = true)
321 {
322 lookup(
323 k,
324 [cb = std::move(cb)](std::vector<std::shared_ptr<Value>>& values, Prefix) { cb(values); },
325 done_cb,
326 exact_match);
327 }
328
336 void insert(Key k, Value v, DoneCallbackSimple done_cb = {})
337 {
338 Prefix p = linearize(k);
339
340 auto lo = std::make_shared<int>(0);
341 auto hi = std::make_shared<int>(p.size_);
342
343 IndexEntry entry;
344 entry.value = v;
345 entry.prefix = p.content_;
346 entry.name = name_;
347
348 Pht::insert(p, entry, lo, hi, clock::now(), true, done_cb);
349 }
350
351private:
363
364 void insert(const Prefix& kp,
365 IndexEntry entry,
366 std::shared_ptr<int> lo,
367 std::shared_ptr<int> hi,
368 time_point time_p,
369 bool check_split,
370 DoneCallbackSimple done_cb = {});
371
372 class Cache
373 {
374 public:
379 void insert(const Prefix& p);
380
388
389 int lookup(const Prefix& p);
390
391 private:
392 static constexpr const size_t MAX_ELEMENT {1024};
393 static constexpr const std::chrono::minutes NODE_EXPIRE_TIME {5};
394
395 struct Node
396 {
397 time_point last_reply; /* Made the assocation between leaves and leaves multimap */
398 std::shared_ptr<Node> parent; /* Share_ptr to the parent, it allow the self destruction of tree */
399 std::weak_ptr<Node> left_child; /* Left child, for bit equal to 1 */
400 std::weak_ptr<Node> right_child; /* Right child, for bit equal to 0 */
401 };
402
403 std::weak_ptr<Node> root_; /* Root of the tree */
404
410 std::multimap<time_point, std::shared_ptr<Node>> leaves_;
411 };
412
413 /* Callback used for insert value by using the pht */
414 using RealInsertCallback = std::function<void(const Prefix& p, IndexEntry entry)>;
415 using LookupCallbackWrapper = std::function<void(std::vector<std::shared_ptr<IndexEntry>>& values, const Prefix& p)>;
416
432 void lookupStep(Prefix k,
433 std::shared_ptr<int> lo,
434 std::shared_ptr<int> hi,
435 std::shared_ptr<std::vector<std::shared_ptr<IndexEntry>>> vals,
436 LookupCallbackWrapper cb,
437 DoneCallbackSimple done_cb,
438 std::shared_ptr<unsigned> max_common_prefix_len,
439 int start = -1,
440 bool all_values = false);
441
449 Prefix zcurve(const std::vector<Prefix>& all_prefix) const;
450
459 virtual Prefix linearize(Key k) const;
460
469 void getRealPrefix(const std::shared_ptr<Prefix>& p, IndexEntry entry, RealInsertCallback end_cb);
470
479 void checkPhtUpdate(Prefix p, IndexEntry entry, time_point time_p);
480
488 static size_t findSplitLocation(const Prefix& compared, const std::vector<std::shared_ptr<IndexEntry>>& vals)
489 {
490 for (size_t i = 0; i < compared.content_.size() * 8 - 1; i++)
491 for (auto const& v : vals)
492 if (Prefix(v->prefix).isContentBitActive(i) != compared.isContentBitActive(i))
493 return i + 1;
494 return compared.content_.size() * 8 - 1;
495 }
496
505 void split(const Prefix& insert,
506 const std::vector<std::shared_ptr<IndexEntry>>& vals,
507 IndexEntry entry,
508 RealInsertCallback end_cb);
509
513 bool validKey(const Key& k) const
514 {
515 return k.size() == keySpec_.size()
516 and std::equal(k.begin(),
517 k.end(),
518 keySpec_.begin(),
519 [&](const Key::value_type& key, const KeySpec::value_type& key_spec) {
520 return key.first == key_spec.first and key.second.size() <= key_spec.second;
521 });
522 }
523
528 void updateCanary(Prefix p);
529
530 const std::string name_;
531 const std::string canary_;
532 const KeySpec keySpec_;
533 Cache cache_;
534 std::shared_ptr<DhtRunner> dht_;
535};
536
537} // namespace indexation
538} // namespace dht
void insert(Key k, Value v, DoneCallbackSimple done_cb={})
Definition pht.h:336
void lookup(Key k, LookupCallback cb={}, DoneCallbackSimple done_cb={}, bool exact_match=true)
std::vector< uint8_t > Blob
Definition utils.h:166
std::string user_type
Definition value.h:656
A blob structure which prefixes a Key in the PHT.
Definition pht.h:32
static unsigned commonBits(const Prefix &p1, const Prefix &p2)
Definition pht.h:124
void swapFlagBit(size_t bit)
Definition pht.h:149
void swapContentBit(size_t bit)
Definition pht.h:144
void addPaddingContent(size_t size)
Definition pht.h:154
Prefix getSibling() const
Definition pht.h:101
bool isFlagActive(size_t pos) const
Definition pht.h:87
bool isContentBitActive(size_t pos) const
Definition pht.h:92
Prefix getPrefix(ssize_t len) const
Definition pht.h:71