Lumiera  0.pre.03
»edit your freedom«
extent-family.hpp
Go to the documentation of this file.
1 /*
2  EXTENT-FAMILY.hpp - maintain a sequence of memory extents used cyclically
3 
4  Copyright (C)
5  2023, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 */
13 
14 
31 #ifndef SRC_VAULT_MEM_EXTENT_FAMILY_H_
32 #define SRC_VAULT_MEM_EXTENT_FAMILY_H_
33 
34 
35 #include "vault/common.hpp"
37 #include "lib/iter-adapter.hpp"
38 #include "lib/nocopy.hpp"
39 #include "lib/util.hpp"
40 
41 #include <algorithm>
42 #include <memory>
43 #include <vector>
44 #include <array>
45 
46 
47 namespace vault{
48 namespace mem {
49  namespace err = lumiera::error;
50 
51  namespace {
52  const size_t ALLOC_SAFETY_LIMIT = 8_GiB;
53  }
54 
55  using util::unConst;
56 
57  template<typename T, size_t siz>
59 
60 
61 
70  template<typename T, size_t siz>
73  {
76  static const size_t EXCESS_ALLOC{5};
77 
78 
79  public:
81  struct Extent
82  : std::array<T,siz>
83  {
84  using Payload = T;
85  using SIZ = std::integral_constant<size_t,siz>;
86  };
87 
88 
89  private:
90  using _UniqueStoragePtr = std::unique_ptr<lib::UninitialisedStorage<T,siz>>;
91 
93  struct Storage
94  : _UniqueStoragePtr
95  {
101  : _UniqueStoragePtr{new lib::UninitialisedStorage<T,siz>}
102  { }
103 
107  Extent&
109  {
110  auto* rawStorage = this->get();
111  ENSURE (rawStorage != nullptr);
112  return static_cast<Extent&> (rawStorage->array());
113  }
114  };
115  using Extents = std::vector<Storage>;
116 
117 
123  struct IdxLink
124  {
125  ExtentFamily* exFam{nullptr};
126  size_t index{0};
127 
128  /* === state protocol API for IterStateWrapper === */
129  bool
130  checkPoint() const
131  {
132  return exFam and index != exFam->after_;
133  }
134 
135  Extent&
136  yield() const
137  {
138  return exFam->access (index);
139  }
140 
141  void
142  iterNext()
143  {
144  index = exFam->incWrap (index);
145  }
146 
147  bool
148  operator== (IdxLink const& oi) const
149  {
150  return exFam == oi.exFam
151  and index == oi.index;
152  }
153 
154 
155  /* === pass-through extended functionality === */
156 
157  size_t getIndex() { return index; }
158 
159  void
160  expandAlloc (size_t cnt =1)
161  {
162  size_t prevStart = exFam->start_;
163  exFam->openNew(cnt);
164  if (index >= prevStart)
165  index += (exFam->start_-prevStart);
166  // was in a segment that might be moved up
167  ENSURE (exFam->isValidPos (index));
168  }
169 
176  void
177  validatePos (Extent* knownTarget)
178  {
179  if (exFam->matchPos (index,knownTarget))
180  return;
181  size_t prevIdx = index;
182  do{
183  iterNext();
184  if (exFam->matchPos (index,knownTarget))
185  return;
186  }
187  while (index != prevIdx);
188  // went full circle without hitting the expected target Extent....
189  throw err::Logic {"Unable to fix-up an iterator after Extent allocation. "
190  "Reference position obsolete or unknown to the memory manager."};
191  }
192  };
193 
194 
195 
196  /* ==== Management Data ==== */
197 
198  Extents extents_;
199  size_t start_,after_;
200 
201  public:
202  explicit
203  ExtentFamily(size_t initialCnt =1)
204  : extents_{initialCnt}
205  , start_{0} // Extents allocated yet marked unused
206  , after_{0}
207  { }
208 
209  void
210  reserve (size_t expectedMaxExtents)
211  { // pertaining management data only
212  extents_.reserve (expectedMaxExtents);
213  }
214 
222  void
223  openNew (size_t cnt =1)
224  {
225  if (not canAccomodate (cnt))
226  {//insufficient reserve => allocate
227  size_t oldSiz = slotCnt();
228  size_t addSiz = cnt - freeSlotCnt()
229  + EXCESS_ALLOC;
230  // add a strike of new extents at the end
231  ___sanityCheckAllocSize (addSiz);
232  extents_.resize (oldSiz + addSiz);
233  if (isWrapped())
234  {// need the new elements in the middle, before the existing start_
235  auto p = extents_.begin();
236  auto first = p + start_;
237  auto mid = p + oldSiz;
238  auto last = p + oldSiz + addSiz;
239  // relocate [fist..mid) after [mid..last)
240  std::rotate (first, mid, last);
241  start_ += addSiz;
242  }
243  }
244  // now sufficient reserve extents are available
245  ENSURE (canAccomodate (cnt));
246  after_ = incWrap (after_, cnt);
247  }
248 
250  void
251  dropOld (size_t cnt)
252  {
253  REQUIRE (cnt <= activeSlotCnt());
254  start_ = incWrap (start_, cnt);
255  }
256 
257 
261 
263  iterator begin() { return iterator{IdxLink{this, start_}}; }
264  iterator end() { return iterator{IdxLink{this, after_}}; }
265 
266  friend iterator begin (ExtentFamily& exFam) { return exFam.begin(); }
267  friend iterator end (ExtentFamily& exFam) { return exFam.end(); }
268 
269 
270  bool empty() const { return start_ == after_; }
271 
275  iterator
277  {
278  REQUIRE (not empty()); // trick to safely decrement by one
279  size_t penultimate = incWrap (after_, slotCnt()-1);
280  return iterator{IdxLink{this, penultimate}};
281  }
282 
283 
284  private: /* ====== storage management implementation ====== */
285  bool
286  isWrapped() const
287  {
288  return after_ < start_;
289  } // note: both are equal only when empty
290 
291  size_t
292  slotCnt() const
293  {
294  return extents_.size();
295  }
296 
298  size_t
300  {
301  REQUIRE (start_ < slotCnt());
302  REQUIRE (after_ <= slotCnt());
303 
304  return not isWrapped()? after_ - start_
305  : (after_ - 0)
306  +(slotCnt() - start_);
307  }
308 
309  size_t
310  freeSlotCnt() const
311  { // always keep one in reserve...
312  REQUIRE (activeSlotCnt() < slotCnt());
313 
314  return slotCnt() - activeSlotCnt();
315  }
316 
317  bool
318  canAccomodate (size_t addCnt) const
319  {
320  return addCnt < freeSlotCnt();
321  } // keep one in reserve to allow for
322  // unambiguous iteration end in wrapped state
323 
327  size_t
328  incWrap (size_t idx, size_t inc =1)
329  {
330  return (idx+inc) % slotCnt();
331  }
332 
333  bool
334  isValidPos (size_t idx) const
335  {
336  REQUIRE (idx < slotCnt());
337  REQUIRE (activeSlotCnt() > 0);
338 
339  return isWrapped()? (start_ <= idx and idx < slotCnt())
340  or idx < after_
341  : (start_ <= idx and idx < after_);
342  }
343 
344  bool
345  matchPos (size_t idx, void* address)
346  {
347  REQUIRE (idx < slotCnt());
348  return address == extents_[idx].get();
349  }
350 
351  Extent&
352  access (size_t idx) const
353  {
354  REQUIRE (isValidPos (idx));
355  return unConst(this)->extents_[idx].access();
356  } // deliberately const-ness does not cover payload
357 
358  void
359  ___sanityCheckAllocSize (size_t addCnt)
360  {
361  size_t resultSiz = slotCnt()+addCnt;
362  size_t requiredSpace = resultSiz * sizeof(Extent);
363  if (requiredSpace > ALLOC_SAFETY_LIMIT)
364  throw err::Fatal{"Raw allocation exceeds safety limit: "
365  +util::showSize(requiredSpace) +" > "
366  +util::showSize(ALLOC_SAFETY_LIMIT)
367  ,err::LUMIERA_ERROR_CAPACITY};
368  }
369 
370 
372  friend class ExtentDiagnostic<T,siz>;
373  };
374 
375 
376 
377 
378 
379 
380 
381  /* ===== Test / Diagnostic ===== */
382 
383  template<typename T, size_t siz>
384  struct ExtentDiagnostic
385  {
386  using ExFam = ExtentFamily<T,siz>;
387 
388  ExFam& exFam_;
389 
390  size_t first() { return exFam_.start_; }
391  size_t last() { return exFam_.after_; }
392  size_t size() { return exFam_.slotCnt(); }
393  size_t active() { return exFam_.activeSlotCnt(); }
394  };
395 
396  template<typename T, size_t siz>
398  watch (ExtentFamily<T,siz>& extentFamily)
399  {
400  return ExtentDiagnostic<T,siz>{extentFamily};
401  }
402 
403 }} // namespace vault::mem
404 #endif /*SRC_VAULT_MEM_EXTENT_FAMILY_H_*/
logical structure of a memory Extent
iterator begin()
iterate over all the currently active Extents
void openNew(size_t cnt=1)
claim next cnt extents, possibly allocate.
Helper template(s) for creating Lumiera Forward Iterators.
Any copy and copy construction prohibited.
Definition: nocopy.hpp:37
iterator last()
positioned to the last / latest storage extent opened
size_t activeSlotCnt() const
Derived specific exceptions within Lumiera&#39;s exception hierarchy.
Definition: error.hpp:190
Mix-Ins to allow or prohibit various degrees of copying and cloning.
Entry in the Extents management datastructure.
Extent & access()
access projected Extent storage type
void dropOld(size_t cnt)
discard oldest cnt extents
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
Block of raw uninitialised storage with array like access.
size_t incWrap(size_t idx, size_t inc=1)
increment index, but wrap at array end.
A raw memory block with proper alignment and array access.
Memory manager to provide a sequence of Extents for cyclic usage.
Basic set of definitions and includes commonly used together (Vault).
Decorator-Adapter to make a »*State Core*« iterable as Lumiera Forward Iterator.
Vault-Layer implementation namespace root.