1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 1998 - 2020 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15
16 #ifndef dealii_vector_memory_h
17 #define dealii_vector_memory_h
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/base/logstream.h>
23 #include <deal.II/base/smartpointer.h>
24 #include <deal.II/base/thread_management.h>
25
26 #include <deal.II/lac/vector.h>
27
28 #include <iostream>
29 #include <memory>
30 #include <vector>
31
32 DEAL_II_NAMESPACE_OPEN
33
34
35 /*!@addtogroup VMemory */
36 /*@{*/
37
38 /**
39 * Memory management base class for vectors. This is an abstract base class
40 * used, among other places, by all iterative methods to allocate space for
41 * auxiliary vectors.
42 *
43 * The purpose of this class is as follows: in iterative solvers and other
44 * places, one needs to allocate temporary storage for vectors, for example
45 * for auxiliary vectors. One could allocate and release them anew every time,
46 * but this may be expensive in some situations if it has to happen very
47 * frequently. A common case for this is when an iterative method is used to
48 * invert a matrix in each iteration of an outer solver, such as when inverting
49 * a matrix block for a Schur complement solver. (step-20 does this, for
50 * example, but instead just keeps a vector around permanently for temporary
51 * storage.)
52 *
53 * In such situations, allocating and deallocating vectors anew in each call
54 * to the inner solver is expensive and leads to memory fragmentation. The
55 * present class allows to avoid this by offering an interface that other
56 * classes can use to allocate and deallocate vectors. Different derived
57 * classes then implement different strategies to provide temporary storage
58 * vectors to using classes.
59 *
60 * For example, the PrimitiveVectorMemory class simply allocates and
61 * deallocates vectors via the operating system facilities (i.e., using
62 * @p new and @p delete) each time it is asked for a vector. It is an
63 * appropriate implementation to use for iterative solvers that are called
64 * only once, or very infrequently.
65 *
66 * On the other hand, the GrowingVectorMemory class never returns memory space
67 * to the operating system memory management subsystem during its lifetime; it
68 * only marks them as unused and allows them to be reused next time a vector
69 * is requested.
70 *
71 *
72 * <h3> Practical use </h3>
73 *
74 * Classes derived from this base class return pointers to new vectors
75 * via the VectorMemory::alloc() function, and re-claim the vector
76 * when it is returned via VectorMemory::free(). These two functions
77 * therefore play a similar role as @p new and @p delete. This
78 * includes the usual drawbacks: It is simple to forget to call
79 * VectorMemory::free() at the end of a function that uses this
80 * facility, or to forget it in an @p if branch of the function where
81 * one has an early @p return from the function. In both cases, this
82 * results in a memory leak: a correct piece of code has to call
83 * VectorMemory::free() for all allocated vectors at <i>all</i>
84 * possible exit points. This includes places where a function is left
85 * because an exception is thrown further down in the call stack and
86 * not explicitly handled here.
87 *
88 * In other words, vectors allocated via VectorMemory::alloc() have
89 * the same issue as raw pointers allocated via @p new: It is easy to
90 * write code that has memory leaks. In the case of raw pointers, the
91 * common solution is to use the std::unique_ptr class instead (see
92 * http://en.cppreference.com/w/cpp/memory/unique_ptr). In the case of
93 * the current class, the VectorMemory::Pointer class is the solution:
94 * it is a class that for all practical purposes looks like a pointer,
95 * but upon destruction also returns the vector back to the
96 * VectorMemory object from which it got it. Since destruction of the
97 * VectorMemory::Pointer class happens whenever it goes out of scope
98 * (whether because the function explicitly returns, or because
99 * control flow leaves it due to an exception), a memory leak cannot
100 * happen: the vector the VectroMemory::Pointer object points to is
101 * <i>always</i> returned.
102 */
103 template <typename VectorType = dealii::Vector<double>>
104 class VectorMemory : public Subscriptor
105 {
106 public:
107 /**
108 * Virtual destructor. This destructor is declared @p virtual to allow
109 * destroying objects of derived type through pointers to this base
110 * class.
111 */
112 virtual ~VectorMemory() override = default;
113
114 /**
115 * Return a pointer to a new vector. The number of elements or their
116 * subdivision into blocks (if applicable) is unspecified and users of this
117 * function should reset vectors to their proper size. The same holds for
118 * the contents of vectors: they are unspecified. In other words,
119 * the place that calls this function will need to resize or reinitialize
120 * it appropriately.
121 *
122 * @warning Just like using <code>new</code> and <code>delete</code>
123 * explicitly in code invites bugs where memory is leaked (either
124 * because the corresponding <code>delete</code> is forgotten
125 * altogether, or because of exception safety issues), using the
126 * alloc() and free() functions explicitly invites writing code
127 * that accidentally leaks memory. You should consider using
128 * the VectorMemory::Pointer class instead, which provides the
129 * same kind of service that <code>std::unique</code> provides
130 * for arbitrary memory allocated on the heap.
131 */
132 virtual VectorType *
133 alloc() = 0;
134
135 /**
136 * Return a vector and indicate that it is not going to be used any further
137 * by the place that called alloc() to get a pointer to it.
138 *
139 * @warning Just like using <code>new</code> and <code>delete</code>
140 * explicitly in code invites bugs where memory is leaked (either
141 * because the corresponding <code>delete</code> is forgotten
142 * altogether, or because of exception safety issues), using the
143 * alloc() and free() functions explicitly invites writing code
144 * that accidentally leaks memory. You should consider using
145 * the VectorMemory::Pointer class instead, which provides the
146 * same kind of service that <code>std::unique</code> provides
147 * for arbitrary memory allocated on the heap.
148 */
149 virtual void
150 free(const VectorType *const) = 0;
151
152 /**
153 * @addtogroup Exceptions
154 * @{
155 */
156
157 /**
158 * Vector was not allocated from this memory pool.
159 */
160 DeclExceptionMsg(
161 ExcNotAllocatedHere,
162 "You are trying to deallocate a vector from a memory pool, but this "
163 "vector has not actually been allocated by the same pool before.");
164
165 //@}
166
167 /**
168 * A class that looks like a pointer for all practical purposes and that
169 * upon construction time allocates a vector from a VectorMemory object
170 * (or an object of a class derived from VectorMemory) that is passed
171 * to the constructor of this class. The destructor then automatically
172 * returns the vector's ownership to the same VectorMemory object.
173 *
174 * Pointers of this type are therefore safe in the sense that they
175 * automatically call VectorMemory::free() when they are destroyed, whether
176 * that happens at the end of a code block or because local variables are
177 * destroyed during exception unwinding. These kinds of object thus relieve
178 * the user from using vector management functions explicitly.
179 *
180 * In many senses, this class acts like <code>std::unique_ptr</code> in that
181 * it is the unique owner of a chunk of memory that it frees upon destruction.
182 * The main differences to <code>std::unique_ptr</code> are (i) that it
183 * allocates memory from a memory pool upon construction, and (ii) that the
184 * memory is not destroyed using `operator delete` but returned to the
185 * VectorMemory pool.
186 */
187 class Pointer
188 : public std::unique_ptr<VectorType, std::function<void(VectorType *)>>
189 {
190 public:
191 /**
192 * Default constructor. This constructor corresponds to a @p nullptr
193 * object that does not own a vector. It can, however, later be
194 * assigned another Pointer object via move assignment in which case
195 * it will steal the vector owned by the other object
196 * (as @p std::unique_ptr does).
197 */
198 Pointer() = default;
199
200 /**
201 * Move constructor: this creates a new Pointer by stealing the internal
202 * data owned by @p p.
203 */
204 Pointer(Pointer &&p) noexcept = default;
205
206 /**
207 * Move operator: this releases the vector owned by the current Pointer
208 * and then steals the internal data owned by @p p.
209 */
210 Pointer &
211 operator=(Pointer &&p) noexcept = default;
212
213 /**
214 * Constructor. This constructor automatically allocates a vector from
215 * the given vector memory object @p mem.
216 */
217 Pointer(VectorMemory<VectorType> &mem);
218
219 /**
220 * Destructor, automatically releasing the vector from the memory pool.
221 */
222 ~Pointer() = default;
223 };
224 };
225
226
227
228 /**
229 * Simple memory management. See the documentation of the base class for a
230 * description of its purpose.
231 *
232 * This class allocates and deletes vectors as needed from the global heap,
233 * i.e. performs no specially adapted actions for memory management.
234 */
235 template <typename VectorType = dealii::Vector<double>>
236 class PrimitiveVectorMemory : public VectorMemory<VectorType>
237 {
238 public:
239 /**
240 * Return a pointer to a new vector. The number of elements or their
241 * subdivision into blocks (if applicable) is unspecified and users of this
242 * function should reset vectors to their proper size. The same holds for
243 * the contents of vectors: they are unspecified. In other words,
244 * the place that calls this function will need to resize or reinitialize
245 * it appropriately.
246 *
247 * For the present class, calling this function will allocate a new vector
248 * on the heap and returning a pointer to it. Later calling free() then
249 * returns the memory to the global heap managed by the operating system.
250 *
251 * @warning Just like using <code>new</code> and <code>delete</code>
252 * explicitly in code invites bugs where memory is leaked (either
253 * because the corresponding <code>delete</code> is forgotten
254 * altogether, or because of exception safety issues), using the
255 * alloc() and free() functions explicitly invites writing code
256 * that accidentally leaks memory. You should consider using
257 * the VectorMemory::Pointer class instead, which provides the
258 * same kind of service that <code>std::unique</code> provides
259 * for arbitrary memory allocated on the heap.
260 */
261 virtual VectorType *
262 alloc() override;
263
264 /**
265 * Return a vector and indicate that it is not going to be used any further
266 * by the instance that called alloc() to get a pointer to it.
267 *
268 * For the present class, this means that the vector is returned to the
269 * global heap.
270 *
271 * @warning Just like using <code>new</code> and <code>delete</code>
272 * explicitly in code invites bugs where memory is leaked (either
273 * because the corresponding <code>delete</code> is forgotten
274 * altogether, or because of exception safety issues), using the
275 * alloc() and free() functions explicitly invites writing code
276 * that accidentally leaks memory. You should consider using
277 * the VectorMemory::Pointer class instead, which provides the
278 * same kind of service that <code>std::unique</code> provides
279 * for arbitrary memory allocated on the heap.
280 */
281 virtual void
282 free(const VectorType *const v) override;
283 };
284
285
286
287 /**
288 * A pool based memory management class. See the documentation of the base
289 * class for a description of its purpose.
290 *
291 * Each time a vector is requested from this class, it checks if it has one
292 * available and returns its address, or allocates a new one on the heap. If a
293 * vector is returned from its user, through the GrowingVectorMemory::free()
294 * member function, it doesn't return the allocated memory to the operating
295 * system memory subsystem, but keeps it around unused for later use if
296 * GrowingVectorMemory::alloc() is called again. The
297 * class therefore avoid the overhead of repeatedly allocating memory on the
298 * heap if temporary vectors are required and released frequently; on the
299 * other hand, it doesn't release once-allocated memory at the earliest
300 * possible time and may therefore lead to an increased overall memory
301 * consumption.
302 *
303 * All GrowingVectorMemory objects of the same vector type use the same memory
304 * pool. (In other words: The pool of vectors from which this class draws is
305 * <i>global</i>, rather than a regular member variable of the current class
306 * that is destroyed at the time that the surrounding GrowingVectorMemory
307 * object is destroyed.) Therefore, functions can create such a
308 * GrowingVectorMemory object whenever needed without the performance penalty
309 * of creating a new memory pool every time. A drawback of this policy is that
310 * vectors once allocated are only released at the end of the program run.
311 */
312 template <typename VectorType = dealii::Vector<double>>
313 class GrowingVectorMemory : public VectorMemory<VectorType>
314 {
315 public:
316 /**
317 * Declare type for container size.
318 */
319 using size_type = types::global_dof_index;
320
321 /**
322 * Constructor. The argument allows to preallocate a certain number of
323 * vectors. The default is not to do this.
324 */
325 GrowingVectorMemory(const size_type initial_size = 0,
326 const bool log_statistics = false);
327
328 /**
329 * Destructor. The destructor also checks that all vectors that have been
330 * allocated through the current object have all been released again.
331 * However, as discussed in the class documentation, this does not imply
332 * that their memory is returned to the operating system.
333 */
334 virtual ~GrowingVectorMemory() override;
335
336 /**
337 * Return a pointer to a new vector. The number of elements or their
338 * subdivision into blocks (if applicable) is unspecified and users of this
339 * function should reset vectors to their proper size. The same holds for
340 * the contents of vectors: they are unspecified. In other words,
341 * the place that calls this function will need to resize or reinitialize
342 * it appropriately.
343 *
344 * @warning Just like using <code>new</code> and <code>delete</code>
345 * explicitly in code invites bugs where memory is leaked (either
346 * because the corresponding <code>delete</code> is forgotten
347 * altogether, or because of exception safety issues), using the
348 * alloc() and free() functions explicitly invites writing code
349 * that accidentally leaks memory. You should consider using
350 * the VectorMemory::Pointer class instead, which provides the
351 * same kind of service that <code>std::unique</code> provides
352 * for arbitrary memory allocated on the heap.
353 */
354 virtual VectorType *
355 alloc() override;
356
357 /**
358 * Return a vector and indicate that it is not going to be used any further
359 * by the instance that called alloc() to get a pointer to it.
360 *
361 * For the present class, this means retaining the vector for later reuse by
362 * the alloc() method.
363 *
364 * @warning Just like using <code>new</code> and <code>delete</code>
365 * explicitly in code invites bugs where memory is leaked (either
366 * because the corresponding <code>delete</code> is forgotten
367 * altogether, or because of exception safety issues), using the
368 * alloc() and free() functions explicitly invites writing code
369 * that accidentally leaks memory. You should consider using
370 * the VectorMemory::Pointer class instead, which provides the
371 * same kind of service that <code>std::unique</code> provides
372 * for arbitrary memory allocated on the heap.
373 */
374 virtual void
375 free(const VectorType *const) override;
376
377 /**
378 * Release all vectors that are not currently in use.
379 */
380 static void
381 release_unused_memory();
382
383 /**
384 * Memory consumed by this class and all currently allocated vectors.
385 */
386 virtual std::size_t
387 memory_consumption() const;
388
389 private:
390 /**
391 * A type that describes this entries of an array that represents
392 * the vectors stored by this object. The first component of the pair
393 * is be a flag telling whether the vector is used, the second
394 * a pointer to the vector itself.
395 */
396 using entry_type = std::pair<bool, std::unique_ptr<VectorType>>;
397
398 /**
399 * The class providing the actual storage for the memory pool.
400 *
401 * This is where the actual storage for GrowingVectorMemory is provided.
402 * Only one of these pools is used for each vector type, thus allocating all
403 * vectors from the same storage.
404 */
405 struct Pool
406 {
407 /**
408 * Standard constructor creating an empty pool
409 */
410 Pool();
411
412 /**
413 * Destructor.
414 */
415 ~Pool();
416
417 /**
418 * Create data vector; does nothing after first initialization
419 */
420 void
421 initialize(const size_type size);
422
423 /**
424 * Pointer to the storage object
425 */
426 std::vector<entry_type> *data;
427 };
428
429 /**
430 * Return an array of allocated vectors.
431 */
432 static Pool &
433 get_pool();
434
435 /**
436 * Overall number of allocations. Only used for bookkeeping and to generate
437 * output at the end of an object's lifetime.
438 */
439 size_type total_alloc;
440
441 /**
442 * Number of vectors currently allocated in this object; used for detecting
443 * memory leaks.
444 */
445 size_type current_alloc;
446
447 /**
448 * A flag controlling the logging of statistics by the destructor.
449 */
450 bool log_statistics;
451
452 /**
453 * Mutex to synchronize access to internal data of this object from multiple
454 * threads.
455 */
456 static Threads::Mutex mutex;
457 };
458
459
460
461 namespace internal
462 {
463 namespace GrowingVectorMemoryImplementation
464 {
465 void
466 release_all_unused_memory();
467 }
468 } // namespace internal
469
470 /*@}*/
471
472 #ifndef DOXYGEN
473 /* --------------------- inline functions ---------------------- */
474
475
476 template <typename VectorType>
Pointer(VectorMemory<VectorType> & mem)477 inline VectorMemory<VectorType>::Pointer::Pointer(VectorMemory<VectorType> &mem)
478 : std::unique_ptr<VectorType, std::function<void(VectorType *)>>(
479 mem.alloc(),
480 [&mem](VectorType *v) { mem.free(v); })
481 {}
482
483
484
485 template <typename VectorType>
486 VectorType *
alloc()487 PrimitiveVectorMemory<VectorType>::alloc()
488 {
489 return new VectorType();
490 }
491
492
493
494 template <typename VectorType>
495 void
free(const VectorType * const v)496 PrimitiveVectorMemory<VectorType>::free(const VectorType *const v)
497 {
498 delete v;
499 }
500
501
502
503 #endif // DOXYGEN
504
505 DEAL_II_NAMESPACE_CLOSE
506
507 #endif
508