iLab Neuromorphic Robotics Toolkit  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AllocationHelpers.H
Go to the documentation of this file.
1 /*! @file
2  @author Shane Grant
3  @copyright GNU Public License (GPL v3)
4  @section License
5  @verbatim
6  // ////////////////////////////////////////////////////////////////////////
7  // The iLab Neuromorphic Robotics Toolkit (NRT) //
8  // Copyright 2010-2012 by the University of Southern California (USC) //
9  // and the iLab at USC. //
10  // //
11  // iLab - University of Southern California //
12  // Hedco Neurociences Building, Room HNB-10 //
13  // Los Angeles, Ca 90089-2520 - USA //
14  // //
15  // See http://ilab.usc.edu for information about this project. //
16  // ////////////////////////////////////////////////////////////////////////
17  // This file is part of The iLab Neuromorphic Robotics Toolkit. //
18  // //
19  // The iLab Neuromorphic Robotics Toolkit is free software: you can //
20  // redistribute it and/or modify it under the terms of the GNU General //
21  // Public License as published by the Free Software Foundation, either //
22  // version 3 of the License, or (at your option) any later version. //
23  // //
24  // The iLab Neuromorphic Robotics Toolkit is distributed in the hope //
25  // that it will be useful, but WITHOUT ANY WARRANTY; without even the //
26  // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR //
27  // PURPOSE. See the GNU General Public License for more details. //
28  // //
29  // You should have received a copy of the GNU General Public License //
30  // along with The iLab Neuromorphic Robotics Toolkit. If not, see //
31  // <http://www.gnu.org/licenses/>. //
32  // ////////////////////////////////////////////////////////////////////////
33  @endverbatim */
34 
35 #ifndef INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_
36 #define INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_
37 
38 #include <map>
40 #include <nrt/Core/Debugging/Log.H>
41 #include <nrt/Core/Memory/details/freelist.h>
42 #include <cstdlib>
43 #include <functional>
44 
45 namespace nrt
46 {
47  namespace memorydetail
48  {
49  //! Trivial allocator that just calls operator new() and operator delete()
51  {
52  void set_debug(bool /*do_debug*/)
53  {
54  // no debug settings for this allocator type
55  }
56 
57  void set_allow_caching(bool /*on*/)
58  {
59  // no caching here in any case
60  }
61 
62  void show_stats(int /*verbosity*/, const char* /*pfx*/,
63  const size_t block_size, const size_t overhead) const
64  {
65  // nothing to do here
66  }
67 
68  void* allocate(size_t nbytes, nrt::rutz::free_list_base** source = 0)
69  {
70  if (source != 0)
71  *source = 0;
72  return ::operator new(nbytes);
73  }
74 
75  void deallocate(void* space, nrt::rutz::free_list_base* source = 0)
76  {
77  assert(source == 0);
78  ::operator delete(space);
79  }
80 
81  void release_free_mem()
82  {
83  // nothing to do here
84  }
85  };
86 
87  //! Caching allocator with free lists for common allocation sizes
88  template <size_t cache_size>
90  {
91  nrt::rutz::free_list_base* cache[cache_size];
92  mutable size_t num_alloc[cache_size];
93  bool allow_caching;
94 
96  : allow_caching(true)
97  {
98  for (size_t i = 0; i < cache_size; ++i)
99  {
100  this->cache[i] = 0;
101  this->num_alloc[i] = 0;
102  }
103  }
104 
105  fastcache_alloc(fastcache_alloc const & other) = delete;
106 
107  ~fastcache_alloc()
108  {
109  release_free_mem();
110  for(size_t i=0; i<cache_size; ++i)
111  delete cache[i];
112  }
113 
114  void set_debug(bool /*do_debug*/)
115  {
116  // no debug settings for this allocator type
117  }
118 
119  void set_allow_caching(bool on)
120  {
121  if (!on && this->allow_caching)
122  {
123  // if we are currently caching but are being asked to turn
124  // off caching, then let's first free any existing caches
125 
126  this->release_free_mem();
127  }
128  this->allow_caching = on;
129  }
130 
131  void show_stats(int verbosity, const char* pfx,
132  const size_t block_size, const size_t overhead) const
133  {
134  size_t nused = 0;
135  size_t bytes_allocated = 0;
136 
137  std::map<size_t, std::string> msgs;
138 
139  for (size_t i = 0; i < cache_size; ++i)
140  if (this->cache[i] != 0)
141  {
142  ++nused;
143  const size_t nb = (this->cache[i]->num_allocations()
144  * this->cache[i]->alloc_size());
145 
146  const size_t extra = (this->cache[i]->num_allocations()
147  - this->num_alloc[i]);
148 
149  this->num_alloc[i] = this->cache[i]->num_allocations();
150 
151  bytes_allocated += nb;
152 
153  if (verbosity <= 0)
154  continue;
155 
156  std::string msg =
157  nrt::sformat("%s%sfastcache[%zu/%zu]: "
158  "%10.4fMB in %zu allocations of %10.4fkB",
159  pfx ? pfx : "", pfx ? ": " : "",
160  i, cache_size, nb / (1024.0*1024.0),
161  this->cache[i]->num_allocations(),
162  this->cache[i]->alloc_size() / 1024.0);
163 
164  if (block_size > 0)
165  {
166  if (this->cache[i]->alloc_size() - overhead >= block_size
167  || this->cache[i]->alloc_size() - overhead <= 1)
168  msg += nrt::sformat(" (%.2fkB * %7.1f + %zuB)",
169  block_size / 1024.0,
170  (double(this->cache[i]->alloc_size() - overhead)
171  / double(block_size)),
172  overhead);
173  else
174  msg += nrt::sformat(" (%.2fkB / %7.1f + %zuB)",
175  block_size / 1024.0,
176  (double(block_size)
177  / double(this->cache[i]->alloc_size() - overhead)),
178  overhead);
179  }
180 
181  if (extra > 0)
182  msg += nrt::sformat(" (+%zu new)", extra);
183 
184  msgs[this->cache[i]->alloc_size()] = msg;
185  }
186 
187  for (std::map<size_t, std::string>::const_iterator
188  itr = msgs.begin(), stop = msgs.end();
189  itr != stop; ++itr)
190  NRT_INFO((*itr).second.c_str());
191 
192 
193  std::string msg =
194  nrt::sformat("%s%sfastcache_alloc<%zu>: %zu/%zu cache table "
195  "entries in use, %fMB total allocated",
196  pfx ? pfx : "", pfx ? ": " : "",
197  cache_size, nused, cache_size,
198  bytes_allocated / (1024.0*1024.0));
199 
200  if (block_size > 0)
201  msg += nrt::sformat(" (%.2fkB * %7.1f)",
202  block_size / 1024.0,
203  double(bytes_allocated) / double(block_size));
204 
205  NRT_INFO(msg.c_str());
206  }
207 
208  // allocate memory block of size nbytes; also return the address
209  // of the nrt::rutz::free_list_base, if any, that was used for
210  // allocation
211  void* allocate(size_t nbytes, nrt::rutz::free_list_base** source)
212  {
213  if (this->allow_caching && source != 0)
214  for (size_t i = 0; i < cache_size; ++i)
215  {
216  if (this->cache[i] != 0)
217  {
218  // we found a filled slot, let's see if it matches our
219  // requested size
220  if (this->cache[i]->alloc_size() == nbytes)
221  {
222  *source = this->cache[i];
223  return this->cache[i]->allocate(nbytes);
224  }
225  // else, continue
226  }
227  else // this->cache[i] == 0
228  {
229  // we found an empty slot, let's set up a new free
230  // list for our requested size:
231  this->cache[i] = new nrt::rutz::free_list_base(nbytes);
232  *source = this->cache[i];
233  return this->cache[i]->allocate(nbytes);
234  }
235  }
236 
237  *source = 0;
238  return ::operator new(nbytes);
239  }
240 
241  // deallocate memory from the given nrt::rutz::free_list_base,
242  // otherwise free it globally
243  void deallocate(void* space, nrt::rutz::free_list_base* source)
244  {
245  if (source != 0)
246  {
247  source->deallocate(space);
248  if (!this->allow_caching)
249  source->release_free_nodes();
250  }
251  else
252  {
253  ::operator delete(space);
254  }
255  }
256 
257  void release_free_mem()
258  {
259  for (size_t i = 0; i < cache_size; ++i)
260  if (this->cache[i] != 0)
261  this->cache[i]->release_free_nodes();
262  }
263  };
264 
265  //! Auxiliary information about an aligned memory allocation
266  template <size_t N>
267  struct alloc_info
268  {
269  struct data_s
270  {
271  // address of ALLOCATED memory, not the address returned to
272  // the user:
273  void* alloc_addr;
274 
275  // the freelist from which this memory was allocated, or else
276  // null:
277  nrt::rutz::free_list_base* source;
278 
279  unsigned long align() const
280  {
281  return reinterpret_cast<unsigned long>(this->alloc_addr) % N;
282  }
283 
284  unsigned long adjust() const
285  {
286  return N-this->align();
287  }
288 
289  void* user_addr() const
290  {
291  return
292  static_cast<char*>(this->alloc_addr)
293  +this->adjust()
294  +N;
295  }
296 
297  unsigned long user_align() const
298  {
299  return reinterpret_cast<unsigned long>(this->user_addr()) % N;
300  }
301 
302  void print() const
303  {
304  NRT_INFO(nrt::sformat("alloc: internal=[%p (align%zu=%lu)], "
305  "user=[%p (align%zu=%lu)]",
306  this->alloc_addr, N, this->align(), this->user_addr(), N, this->user_align()));
307  }
308 
309  };
310  data_s data;
311  static const int pad_size = int(N) - int(sizeof(data_s));
312  static_assert(pad_size >= 0, "Minimum alignment size is 16 bytes");
313  char pad[pad_size];
314  };
315 
316  //! Allocate memory that is aligned on an N-byte boundary
317  template <class src_type, size_t N>
319  {
320  src_type src_alloc;
321 
322  bool do_debug_printing;
323  double nbytes_allocated;
324  size_t nallocations;
325  size_t nbytes_current;
326  size_t nallocations_current;
327 
328  struct assertions
329  {
330  static_assert(sizeof(alloc_info<N>) == N, "Sizeof assumptions about alloc_info are wrong!");
331  };
332 
333  aligned_alloc()
334  :
335  do_debug_printing(false),
336  nbytes_allocated(0.0),
337  nallocations(0),
338  nbytes_current(0),
339  nallocations_current(0)
340  {}
341 
342  aligned_alloc(aligned_alloc const & other) = delete;
343 
344  void set_debug(bool do_debug)
345  {
346  this->do_debug_printing = do_debug;
347 
348  // also call set_debug() on our child object
349  src_alloc.set_debug(do_debug);
350  }
351 
352  void set_allow_caching(bool on)
353  {
354  src_alloc.set_allow_caching(on);
355  }
356 
357  void show_stats(int verbosity, const char* pfx,
358  const size_t block_size, const size_t overhead) const
359  {
360  NRT_INFO(nrt::sformat("%s%saligned_alloc<%zu>: "
361  "all-time: [%fMB in %zu allocations], "
362  "current: [%fMB in %zu allocations]",
363  pfx ? pfx : "",
364  pfx ? ": " : "",
365  N,
366  double(this->nbytes_allocated)/(1024.0*1024.0), this->nallocations,
367  double(this->nbytes_current)/(1024.0*1024.0), this->nallocations_current));
368 
369  // also show stats for our child object
370  src_alloc.show_stats(verbosity, pfx, block_size, overhead+2*N);
371  }
372 
373  void* allocate(size_t user_nbytes)
374  {
375  alloc_info<N> info;
376  info.data.source = 0;
377 
378  // We request extra space beyond what the user wants -- N extra
379  // bytes allow us to return an address to the user that is
380  // aligned to a N-byte boundary, and sizeof(alloc_info<N>) extra
381  // bytes allow us to stick some auxiliary info just ahead of the
382  // address that we return to the user. Note that for convenience
383  // we have set things up so that sizeof(alloc_info<N>)==N, so
384  // the number of extra bytes that we need is just 2*N.
385  size_t alloc_nbytes = user_nbytes+2*N;
386 
387  info.data.alloc_addr =
388  this->src_alloc.allocate(alloc_nbytes, &info.data.source);
389 
390  /* We will set things up like this:
391 
392  +- address = return value of src_alloc.allocate()
393  |
394  | +- address = return value
395  | | of this function
396  v v
397 
398  +------------------+-------------------+------------------------+
399  | len==adjust | len==N | len==user_nbytes |
400  | contents: | contents: | contents: |
401  | unused | alloc_info<N> | empty space for user |
402  | alignment: | alignment: | alignment: |
403  | unknown | N-byte boundary | N-byte boundary |
404  +------------------+-------------------+------------------------+
405 
406 */
407 
408  void* const user_addr = info.data.user_addr();
409 
410  static_cast<alloc_info<N>*>(user_addr)[-1].data = info.data;
411 
412  //this->nbytes_allocated += info.data.alloc_nbytes;
413  ++this->nallocations;
414  //this->nbytes_current += info.data.alloc_nbytes;
415  ++this->nallocations_current;
416 
417  if (this->do_debug_printing)
418  {
419  info.data.print();
420  this->show_stats(0, 0, 0, 0);
421  }
422 
423  return user_addr;
424  }
425 
426  void deallocate(void* user_addr)
427  {
428  const alloc_info<N>* const info =
429  static_cast<alloc_info<N>*>(user_addr) - 1;
430 
431  //this->nbytes_current -= info->data.alloc_nbytes;
432  --this->nallocations_current;
433 
434  if (this->do_debug_printing)
435  {
436  info->data.print();
437  this->show_stats(0, 0, 0, 0);
438  }
439 
440  this->src_alloc.deallocate(info->data.alloc_addr, info->data.source);
441  }
442 
443  void release_free_mem()
444  {
445  this->src_alloc.release_free_mem();
446  }
447  };
448  } // namespace memorydetail
449 } // namespace nrt
450 
451 #endif // INCLUDE_NRT_CORE_MEMORY_DETAILS_ALLOCATIONHELPERS_H_