· 7 years ago · Oct 25, 2018, 04:30 AM
1#pragma once
2
3#include <swLib/util/ChildOf.hpp>
4#include <swLib/util/noneOf.hpp>
5#include <swLib/crypto/crypto.h>
6
7namespace sw::memory {
8
9///<summary>
10/// HandleTable - A table of slots, each containing a type, addressible by
11/// a Handle, which is a combination of two numbers, a sequence (indicating the
12/// instance id of the allocated handle object), and an index (indicating where
13/// in this table's static array of slots the slot exists in).
14///</summary>
15template<typename Type, int32_t MaxSlots = 1000>
16class HandleTable final
17{
18public:
19 HandleTable() noexcept = default;
20 ~HandleTable() noexcept
21 {
22 for (auto &slot : slots_)
23 slot.release();
24 }
25
26 // No copy, no move
27 HandleTable(const HandleTable &table) noexcept = delete;
28 HandleTable & operator = (const HandleTable &table) noexcept = delete;
29
30 HandleTable(HandleTable &&table) noexcept = delete;
31 HandleTable & operator = (HandleTable &&table) noexcept = delete;
32
33 //
34 // Handle - Effectively a number, containing two fields a sequence, and
35 // an index, both referencing a slot in the table. Type safe to prevent
36 // ambiguity.
37 //
38 struct Handle
39 {
40 int32_t sequence_ = 0;
41 int32_t index_ = 0;
42
43 auto valid() const noexcept
44 {
45 if (sequence_ == 0)
46 return false;
47
48 if (index_ >= MaxSlots || index_ < 0)
49 return false;
50
51 return true;
52 }
53
54 void reset() noexcept
55 {
56 sequence_ = 0;
57 index_ = 0;
58 }
59
60 explicit operator bool() const noexcept
61 {
62 return valid();
63 }
64
65 Str __toString() const noexcept
66 {
67 if (valid())
68 return toString(string::toHex(sequence_), "-", string::toHex(index_));
69 return "{Invalid}";
70 }
71 };
72
73private:
74
75 //
76 // STATE - The slot exists in exactly one of the following states, each state
77 // describes the assumptions which can be made on the slot, making the slot
78 // into a mini state machine of sorts.
79 //
80 enum class STATE
81 {
82 Init, // Handle is in its initialized default state
83
84 Reserved, // The slot has been reserved for allocation
85
86 Allocated, // The object has been allocated, no gets/puts allowed
87
88 Ready, // Open for buisiness, get/puts are allowed, object is allocated
89
90 NotReady, // Allocated, no gets allowed, puts allowed, and when refCount drops
91 // to zero, the object will be destroyed and the slot set back to Init
92 };
93
94 //
95 // Slot - A slot is an entry in the statically constructed array within the
96 // HandleTable. It contains atomically modified fields to synchronize access
97 // and broker construction and deconstruction of the held object templated type.
98 //
99 struct Slot
100 {
101 // A very primitive lock whih we spin hard on, there is no real
102 // contention here requiring a context switch
103 std::atomic_flag lock_;
104
105 // The number of check outs which have been made for this
106 // slot, refCount_ must drop to zero before the held object
107 // may be destroyed
108 std::atomic<int32_t> refCount_ = {0};
109
110 // The currently bound sequence, bound from the randomly initiated
111 // then sequentially incremented sequence field in the HandleTable
112 // this prevents us from allowing handles from other tables to be valid
113 // (At least not without chance on our side), due to the type of the
114 // handle table itself, it implicitly prevent cross types from
115 // being incorrectly casted (hence no group field in the c++ version of handles).
116 int32_t sequence_ = 0;
117
118 // Here is where the object lives, its constructed when this slot is allocated
119 // and reset when released.
120 std::optional<Type> object_;
121
122 // The current state of this slot
123 STATE state_ = STATE::Init;
124
125 void lock() noexcept
126 {
127 while (lock_.test_and_set(std::memory_order_acquire)) {}
128 }
129
130 void unlock() noexcept
131 {
132 lock_.clear();
133 }
134
135 //
136 // tryLock - Without spinning, attempts to atomically set the lock flag.
137 // Returns true upon successful locking, false if it failed.
138 //
139 auto tryLock() noexcept
140 {
141 return !lock_.test_and_set(std::memory_order_acquire);
142 }
143
144 //
145 // release - Clears state in this slot, destroys the bound object, sets
146 // state back to Init.
147 //
148 void release() noexcept
149 {
150 refCount_ = 0;
151 sequence_ = 0;
152 object_.reset();
153 state_ = STATE::Init;
154 }
155 };
156
157 //
158 // SlotInfo - When a slot is looked up, and its handle is valid, and/or whatever
159 // extra checks were made were valid, this then is instantiated to reference the
160 // slot.
161 //
162 struct SlotInfo
163 {
164 std::reference_wrapper<Slot> slot_;
165 const int32_t index_;
166
167 // De-ref accesses the internal slot reference
168 auto operator -> () const { return &slot_.get(); }
169 auto operator -> () { return &slot_.get(); }
170 };
171
172 // Allow the handle ptr class to call the internal apis
173 friend class Ptr;
174
175public:
176 //
177 // Ptr - The user facing object which contains the checked out
178 // reference to the handle, and provides apis to manage the handles
179 // lifetime
180 //
181 class Ptr : util::ChildOf<HandleTable *>
182 {
183 public:
184 using Parent = util::ChildOf<HandleTable *>;
185 using Parent::parent;
186 using Parent::parent_;
187
188 Ptr() noexcept :
189 Parent(nullptr)
190 {
191 }
192
193 Ptr(HandleTable *parent, Handle handle, std::optional<std::reference_wrapper<Type>> &&object = {}) noexcept :
194 Parent(parent),
195 handle_(handle),
196 object_(_mv(object))
197 {
198 }
199
200 Ptr(const Ptr &ptr) noexcept :
201 Parent(ptr.parent())
202 {
203 operator = (ptr);
204 }
205
206 Ptr & operator = (const Ptr &ptr) noexcept
207 {
208 if (this == &ptr)
209 return *this;
210
211 // Put if we have one checked out
212 put();
213
214 // Update the parent
215 parent_ = ptr.parent();
216
217 // Copy the handle, don't increment the ref, get will occur again
218 handle_ = ptr.handle_;
219
220 return *this;
221 }
222
223 Ptr(Ptr &&ptr) noexcept :
224 Parent(ptr.parent())
225 {
226 operator = (_mv(ptr));
227 }
228
229 Ptr & operator = (Ptr &&ptr) noexcept
230 {
231 // Put our ptr if needed
232 put();
233
234 // Move everything over
235 parent_ = ptr.parent_;
236 handle_ = ptr.handle_;
237 object_ = _mv(ptr.object_);
238
239 // And empty them
240 ptr.parent_ = nullptr;
241 ptr.handle_.reset();
242 ptr.object_.reset();
243
244 return *this;
245 }
246
247 ~Ptr() noexcept
248 {
249 put();
250 }
251
252 //
253 // get - Attempts to fetch the object ref if one wasn't already
254 // stashed, throws upon error, otherwise always returns a non
255 // const reference to the held object instance.
256 //
257 auto & get() const noexcept(false)
258 {
259 if (object_)
260 return object_.value().get();
261
262 if (!parent())
263 SWERR_THROW(RuntimeError, "Invalid handle ptr");
264
265 std::visit(
266 [&](auto &&result) {
267 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
268 // Failed, throw
269 throw result;
270 } else {
271 // Got it, stash it
272 object_ = {std::forward<_typeof(result)>(result)};
273 }
274 },
275 parent()->get(handle_)
276 );
277
278 return object_.value().get();
279 }
280
281 //
282 // put - Puts the held object instance ptr back into the handle table,
283 // decrementing its ref count
284 //
285 auto put() const noexcept
286 {
287 if (parent() && object_) {
288 object_.reset();
289 parent()->put(handle_);
290 }
291 }
292
293 //
294 // setNotReady - Attempts to flag this handle as not ready, if
295 // successful and the handle may be used as it will have the
296 // final check out to the object. Once put, it will be destroyed.
297 //
298 auto & setNotReady(bool checkout = true) noexcept
299 {
300 put();
301
302 // No parent, nothing to do
303 if (!parent())
304 return *this;
305
306 return std::visit(
307 [&](auto &&result)->decltype(auto) {
308 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
309 // Failed, return a ref to ourselves, we'll evaluate to
310 // false on a boolean check
311 return *this;
312 } else {
313 // Success, stash the resulting reference and return ourselves
314 // we'll evaluate to true indicating we successfully marked
315 // this as not ready
316 object_ = {std::forward<_typeof(result)>(result)};
317 return *this;
318 }
319 },
320 parent()->setNotReady(handle_, checkout)
321 );
322 }
323
324 // The de-reference operator will implicitly check out a ptr
325 // to the handle, and return a ptr to its reference
326 Type * operator -> () noexcept(false)
327 {
328 return &get();
329 }
330
331 const Type * operator -> () const noexcept(false)
332 {
333 return &get();
334 }
335
336 //
337 // operator bool - Returns true if this is a valid handle, will also ask
338 // the handle manager if we're valid. If this returns true you will be
339 // guaranteed to dereference without a throw.
340 //
341 explicit operator bool() const noexcept
342 {
343 return valid();
344 }
345
346 //
347 // refCount - Returns the number of references the current handle has.
348 // Negative value returned on error, no implicit checkout occurs here.
349 //
350 int32_t refCount() const noexcept
351 {
352 if (!handle_)
353 return -1;
354 auto res = parent()->refCount(handle_);
355 if (std::holds_alternative<int32_t>(res))
356 return std::get<int32_t>(res);
357 return -1;
358 }
359
360 //
361 // reset - The standard method that will clear the ownership and handle value
362 // from this object.
363 //
364 void reset() noexcept
365 {
366 if (handle_) {
367 put();
368 handle_ = {};
369 parent_ = nullptr;
370 }
371 }
372
373 //
374 // valid - Performs either a loose check or a hard re-put/get based on
375 // what the use case is.
376 //
377 bool valid(bool doubleCheck = false) const noexcept
378 {
379 if (parent() && handle_) {
380
381 // Force a re-get to check for not ready if doubleCheck is true
382 if (doubleCheck)
383 put();
384 else if (object_)
385 return true;
386
387 // Don't have one checked out, get one
388 auto res = parent()->get(handle_);
389 if (std::holds_alternative<error::Exception>(res))
390 return false;
391
392 // Got it
393 object_ = _mv(std::get<std::optional<std::reference_wrapper<Type>>>(res));
394 return true;
395 }
396 return false;
397 }
398
399 private:
400 // Our optional reference to the stored object, once set
401 // we can safely access it without fear of it going away
402 mutable std::optional<std::reference_wrapper<Type>> object_;
403
404 // The handle describes what slot this ptr is referencing, its passed
405 // to the table anytime we need to check it out or put it etc.
406 Handle handle_;
407 };
408
409private:
410 // Define the lookup result, which pairs an exception, with a slot info in a variant
411 // only one may be set, allowing less if statements using std::visit based on the
412 // contents
413 using LookupResult = std::variant<error::Exception, SlotInfo>;
414
415 //
416 // lookup - Validates the handle sequence and index, and returns a SlotInfo
417 // in the success case, an error::Exception in the failure case.
418 //
419 LookupResult lookup(Handle handle) noexcept
420 {
421 if (!handle.valid())
422 return {SWERR_MAKE(InvalidArgument, "Invalid handle:", handle)};
423
424 return SlotInfo{{slots_[handle.index_]}, handle.index_};
425 }
426
427 //
428 // lookup - Looks up the slot, validates the handle, and always locks the slot. Optionally
429 // keeps the slot locked, and optionally validates the slot state matches any of the optional
430 // states provided.
431 //
432 LookupResult lookup(Handle handle, bool keepLocked, std::optional<std::vector<STATE>> states = {}) noexcept
433 {
434 return std::visit(
435 [&](auto &&result)->LookupResult {
436 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
437 // Newp we failed to look it up, forward the error along
438 return {_mv(result)};
439 } else {
440 // Well the handle is grossly valid, now lock it
441 result->lock();
442
443 // Guard the lock
444 auto unlockGuard = util::ScopeImpl([&]{ result->unlock(); });
445
446 // If state check requested, make sure its any of them
447 if (states && util::noneOf(states.value(),
448 [&](const auto &state) { return result->state_ == state; }))
449 return SWERR_MAKE(InvalidArgument, "Required handle state not found:", handle);
450
451 // Leave it locked if they want it so
452 if (keepLocked)
453 unlockGuard.cancel();
454
455 // And return them the slot info ref
456 return {_mv(result)};
457 }
458 },
459 // Do a basic lookup with no checks, this will validate the sanity of the handle
460 lookup(handle)
461 );
462 }
463
464 // Define the get result, if successful a reference to the type is returned, otherwise
465 // an exception is returned.
466 using GetResult = std::variant<error::Exception, std::optional<std::reference_wrapper<Type>>>;
467
468 //
469 // get - Attempts to lookup the handle, if the state is valid and the slot is in a ready state
470 // the reference count will be incremented and a reference to the object returned.
471 //
472 GetResult get(Handle handle) noexcept
473 {
474 return std::visit(
475 [&](auto &&result)->GetResult {
476 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
477 // Newp, forward the error
478 return {_mv(result)};
479 } else {
480 // Success, increment the ref count, then unlock and return a reference
481 result->refCount_++;
482
483 LOGT(HANDLE, "Get:", handle, result->refCount_);
484
485 result->unlock();
486
487 return std::optional<std::reference_wrapper<Type>>{{result->object_.value()}};
488 }
489 },
490 lookup(handle, true, {{STATE::Ready}})
491 );
492 }
493
494 //
495 // refCount - Returns the number of checked out references the handle has
496 //
497 std::variant<error::Exception, int32_t> refCount(Handle handle) noexcept
498 {
499 return std::visit(
500 [&](auto &&result)->std::variant<error::Exception, int32_t> {
501 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
502 // Newp, forward the error
503 return {_mv(result)};
504 } else {
505 // Success, return the ref count
506 int32_t refCount = result->refCount_;
507
508 result->unlock();
509 return {refCount};
510 }
511 },
512 // To get a refcount, the handle must either be in a ready or not ready state
513 lookup(handle, true, {{{STATE::Ready}, {STATE::NotReady}}})
514 );
515 }
516
517 //
518 // put - Puts the reference the caller is holding by decrementing the ref count, if the handle
519 // is in a not ready state, the object will be destroyed.
520 //
521 std::optional<error::Exception> put(Handle handle) noexcept
522 {
523 return std::visit(
524 [&](auto &&result)->std::optional<error::Exception> {
525 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
526 // Newp, forward the error
527 return {_mv(result)};
528 } else {
529 // Success, dec the ref (its locked)
530 SW_ASSERT(result->refCount_ > 0);
531
532 LOGT(HANDLE, "Put:", handle, result->refCount_);
533
534 result->refCount_--;
535
536 // Handle the not ready destroy case
537 if (result->state_ == STATE::NotReady && result->refCount_ == 0) {
538 LOGT(HANDLE, "Release:", handle, result->refCount_);
539
540 result->release();
541
542 // Unlock and set the next free slot after we unlock
543 result->unlock();
544 nextFreeIndex_ = handle.index_;
545 return {};
546 }
547
548 // Unlock without setting next free
549 result->unlock();
550
551 return {};
552 }
553 },
554 // To put, the handle must either be in a ready or not ready state
555 lookup(handle, true, {{{STATE::Ready}, {STATE::NotReady}}})
556 );
557 }
558
559 // Define the result for the not ready call, similar to get, either an exception, or an optional
560 // final reference to the object representing the final checkout will be returned.
561 using NotReadyResult = GetResult;
562
563 //
564 // setNotReady - Flags the handle as not ready (if the handle is valid that is),
565 // which will prevent further gets, and on the final put the handle will be destroyed.
566 // Optionally allows the caller to atomically get the final check out themselves.
567 //
568 NotReadyResult setNotReady(Handle handle, bool get = true) noexcept
569 {
570 return std::visit(
571 [&](auto &&result)->NotReadyResult {
572 if constexpr(std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
573 // Newp we failed to look it up, forward the error along
574 return {_mv(result)};
575 } else {
576 // Always have to unlock
577 auto unlockGuard = util::ScopeImpl([&]{ result->unlock(); });
578
579 LOGT(HANDLE, "NotReady:", handle, result->refCount_);
580
581 // The handle is locked now, set state to not ready
582 result->state_ = STATE::NotReady;
583
584 // If a final ref was requested
585 if (get) {
586 // Increment the ref now
587 result->refCount_++;
588
589 LOGT(HANDLE, "Get:", handle, result->refCount_);
590
591 // And return the ref
592 return std::optional<std::reference_wrapper<Type>>{result->object_.value()};
593 }
594
595 // If the ref count is 0, destroy
596 if (result->refCount_ == 0) {
597 result->release();
598
599 // Unlock and set the next free hint
600 unlockGuard.exec();
601
602 nextFreeIndex_ = handle.index_;
603 }
604
605 // No result, all done
606 return std::optional<std::reference_wrapper<Type>>{};
607 }
608 },
609 // Lookup the ready handle and return it locked
610 lookup(handle, true, {{STATE::Ready}})
611 );
612 }
613
614 // Reserve will look like a lookup result wise, the slot will be locked, and
615 // the state set to Reserved
616 using ReserveResult = LookupResult;
617
618 //
619 // reserve - Looks up a new slot, using the nextSlot_ index as a hint as to where
620 // to start its iteration in the slot table. Each thread here will 'race' to
621 // lock a slot, to set its state to Reserved.
622 ReserveResult reserve() noexcept
623 {
624 // Use the hint and atomically increment it for the next guy
625 int32_t startIndex;
626
627 // Fix the wrap
628 if (nextFreeIndex_ < 0 || nextFreeIndex_ >= MaxSlots)
629 nextFreeIndex_ = 0;
630
631 // Increment and continue to reserve
632 startIndex = nextFreeIndex_++;
633
634 // Two passes, first will use the hint, second will start at the front
635 for (auto pass = 1; pass <= 2; pass++) {
636 // Second pass
637 if (pass == 2) {
638 // If we didn't already start at 0, we're done
639 if (startIndex == 0)
640 break;
641
642 // Start at zero and find a free slot
643 startIndex = 0;
644 }
645
646 for (auto index = startIndex; index < MaxSlots; index++) {
647 auto &slot = slots_[index];
648
649 // Try to lock the slot, proceed to the next otherwise
650 if (!slot.tryLock())
651 continue;
652
653 // We locked it, see if its available for use
654 if (slot.state_ != STATE::Init) {
655 slot.unlock();
656 continue;
657 }
658
659 // Fantastic, set it reserved
660 slot.state_ = STATE::Reserved;
661
662 LOGT(HANDLE, "Reserve:", string::toHex(index), slot.refCount_);
663
664 // Leave it locked and return a new slot info object inline
665 return SlotInfo{{slot}, index};
666 }
667 }
668
669 // Failed to find a free one, return error
670 dev::enterDebugger();
671 return {SWERR_MAKE(RuntimeError, "Out of slots")};
672 }
673
674public:
675 //
676 // allocate - Reserves a new slot, and constructs the object, then marks the slot
677 // as ready. The Checkout template argument when true will cause this to return a Ptr
678 // ready to go with a checked out reference to the object.
679 //
680 template<bool Checkout = true, typename ...Args>
681 Ptr allocate(Args && ... args) noexcept(false)
682 {
683 // Now move it into place in the visit
684 return std::visit(
685 [this,&args...](auto &&result) mutable ->Ptr {
686 if constexpr(!std::is_base_of_v<std::exception, std::decay_t<_typeof(result)>>) {
687 SW_ASSERT(result->state_ == STATE::Reserved);
688
689 LOGT(HANDLE, "Allocated:", string::toHex(result.index_));
690
691 // Great, lock is held now, change state to allocated
692 result->state_ = STATE::Allocated;
693
694 // Release the lock while we construct
695 result->unlock();
696
697 // Create a guard if it throws
698 auto releaseGuard = util::ScopeImpl([&]{
699 // Release the slot atomically
700 result->lock();
701 result->release();
702 result->unlock();
703 });
704
705 // Now construct in place
706 result->object_.emplace(std::forward<Args>(args)...);
707
708 // Release the guard now, and re-lock
709 releaseGuard.cancel();
710 result->lock();
711
712 // Success, mark the handle as Ready, and bind the sequence id
713 // to the current one
714 result->state_ = STATE::Ready;
715 result->sequence_ = sequence_++;
716
717 LOGT(HANDLE, "Ready:", Handle{result->sequence_, result.index_});
718
719 // If they want it pre-checked out, do that
720 if constexpr(Checkout) {
721 SW_ASSERT(result->refCount_ == 0);
722 result->refCount_++;
723 SW_ASSERT(result->refCount_ == 1);
724
725 LOGT(HANDLE, "Get:", Handle{result->sequence_, result.index_}, result->refCount_);
726
727 result->unlock();
728
729 return {this, {result->sequence_, result.index_}, result->object_.value()};
730 }
731
732 result->unlock();
733
734 // Construct a Ptr inline no pre-checkout
735 return {this, {result->sequence_, result.index_}};
736 } else {
737 // Failed, throw the error
738 throw result;
739 }
740 },
741 reserve()
742 );
743 }
744
745private:
746 // The next sequence, initialized to a random positive value, not including
747 // the value 1
748 std::atomic<int32_t> sequence_ = {crypto::randomNumber<int32_t>(1)};
749
750 // The static array containing all possible slots
751 std::array<Slot, MaxSlots> slots_;
752
753 // A hint where we may find the next free slot
754 std::atomic<int32_t> nextFreeIndex_ = {crypto::randomNumber<int32_t>(0, MaxSlots)};
755};
756
757} // namespace sw::memory