replicode
memory.h
Go to the documentation of this file.
1 /*
2  * HUMANOBS - mBrane
3  *
4  * Eric Nivel
5  * Center for Analysis and Design of Intelligent Agents
6  * Reykjavik University, Menntavegur 1, 101 Reykjavik, Iceland
7  * http://cadia.ru.is
8  * Copyright(c)2012
9  *
10  * This software was developed by the above copyright holder as part of
11  * the HUMANOBS EU research project, in collaboration with the
12  * following parties:
13  *
14  * Autonomous Systems Laboratory
15  * Technical University of Madrid, Spain
16  * http://www.aslab.org/
17  *
18  * Communicative Machines
19  * Edinburgh, United Kingdom
20  * http://www.cmlabs.com/
21  *
22  * Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
23  * University of Lugano and SUPSI, Switzerland
24  * http://www.idsia.ch/
25  *
26  * Institute of Cognitive Sciences and Technologies
27  * Consiglio Nazionale delle Ricerche, Italy
28  * http://www.istc.cnr.it/
29  *
30  * Dipartimento di Ingegneria Informatica
31  * University of Palermo, Italy
32  * http://roboticslab.dinfo.unipa.it/index.php/Main/HomePage
33  *
34  *
35  * --- HUMANOBS Open-Source BSD License, with CADIA Clause v 1.0 ---
36  *
37  * Redistribution and use in source and binary forms, with or without
38  * modification, is permitted provided that the following conditions
39  * are met:
40  *
41  * - Redistributions of source code must retain the above copyright
42  * and collaboration notice, this list of conditions and the
43  * following disclaimer.
44  *
45  * - Redistributions in binary form must reproduce the above copyright
46  * notice, this list of conditions and the following
47  * disclaimer in the documentation and/or other materials provided
48  * with the distribution.
49  *
50  * - Neither the name of its copyright holders nor the names of its
51  * contributors may be used to endorse or promote products
52  * derived from this software without specific prior written permission.
53  *
54  * - CADIA Clause: The license granted in and to the software under this
55  * agreement is a limited-use license. The software may not be used in
56  * furtherance of:
57  * (i) intentionally causing bodily injury or severe emotional distress
58  * to any person;
59  * (ii) invading the personal privacy or violating the human rights of
60  * any person; or
61  * (iii) committing or preparing for any act of war.
62  *
63  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
64  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
65  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
66  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
67  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
68  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
69  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
70  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
71  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
72  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
73  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
74  */
75 
76 #ifndef mBrane_sdk_memory_h
77 #define mBrane_sdk_memory_h
78 
79 #include <cstdlib>
80 
81 #include "../CoreLibrary/utils.h"
82 #include "config.h"
83 #include "array.h"
84 
85 
86 namespace mBrane
87 {
88 namespace sdk
89 {
90 
91 // Memory allocator.
92 // One instance of Memory handles the allocation for instances of a given (fixed) size.
93 // Memory holds statically as many instances of Memory as there are instance sizes (in 64 times a power of 2) to provide allocation for.
94 // Retrieving the right Memory instance given a size requires a lock: for the sake of efficiency, threads are supposed to
95 // keep a reference on the Memory instance they use. For example, this is implemented in the Object class as a class
96 // variable (_Allocator) that is initialized once and kept throughout the process execution.
97 #ifdef MEMORY_1
98 // Memory allocation is provided as segments of a larger block. Blocks are allocated to a certain size (objectSize x objectCount), and linked together
99 // objectSize is the smallest power of two minus one greater or equal than the object's size; objectSize start at 64 bytes.
100 // Each Memory always holds at least one block, even if entirely free.
101 class mBrane_dll Memory
102 {
103 private:
105  static std::mutex s_mutex;
106  // Blocks hold contiguous data storage, i.e. an array of segments (byte arrays of size objectSize)
107  // When not allocated, a segment contains a pointer to the next free segment: that's its first sizeof(uint8_t *) bytes
108  // When deallocated, a segment is not initialized (except the pointer to the next free segment)
109  // When allocated a segment contains the address of its block (first sizeof(Block *) bytes) - for speeding up deallocation:
110  // this means that the allocated object starts at segment+sizeof(Block *)
111  // Blocks are allocated by malloc(sizeof(Block)+totalSize) and deallocated by free()
112  // Segments are allocated just after freeObjects, i.e. at ((uint8_t *)this)+sizeof(Block)
113  // Synchronization between alloc() and dealloc() uses locks: each call to alloc() or dealloc() enters a critical section, regardless of the contention
114  class Block
115  {
116  friend class Memory;
117  private:
120  const size_t objectSize; // power of 2; includes the pointer to the block
121  const size_t totalSize; // objectCount x objectSize
124  uint8_t *firstFree; // first free cell
125  void *operator new(size_t s, size_t objectSize, uint16_t objectCount);
126  void operator delete(void *b);
127  Block(size_t objectSize, uint16_t objectCount);
128  ~Block();
129  void *alloc(); // first sizeof(Block *) bytes initialized to this, the rest is initialized to 0
130  void dealloc(void *s); // s is a segment, not an object; first sizeof(uint8_t *) bytes initialized to the next free segment, the rest is left untouched
131  };
132  const size_t objectSize;
135  Block *emptyBlock; // address of the empty block in the block list, if any; NULL otherwise
137  std::mutex m_mutex;
138  Memory(size_t objectSize);
139  void *operator new(size_t s, uint16_t index);
140  void operator delete(void *b);
141  static size_t GetNormalizedSize(size_t s, uint8_t &pow2); // converts a size into the next power of 2
142 public:
143  static Memory *GetStatic(size_t s); // called at class loading time; sequential calls
144  static Memory *GetDynamic(size_t s); // called dynamically (rwa storage); concurrent calls
145  Memory(); // do NOT use
146  ~Memory();
147  const uint32_t getObjectSize() const;
148  void *alloc();
149  void *alloc(uint32_t &normalizedSize); // same as alloc; returns the allocated size as a power of 2
150  void dealloc(void *o);
151 };
152 #elif defined MEMORY_2
153 // Memory allocation is provided as segments of a larger block. Blocks are allocated to a certain size (segmentSize x segmentCount), and linked together
154 // segmentSize is the smallest power of two minus one greater or equal than the object's size; segmentSize start at 64 bytes.
155 // Each Memory always holds at least one block, even if entirely free.
156 class mBrane_dll Memory
157 {
158 private:
159  static Array<Memory, 16> *Memories;
160  static CriticalSection *CS;
161  // Blocks hold contiguous data storage, i.e. an array of segments (byte arrays of size objectSize)
162  // A segment is a pointer to the block (first sizeof(Block *) bytes) followed by allocation space (objectSize-sizeof(Block*)
163  // This means that the allocated object starts at segment+sizeof(Block *)
164  // Blocks are allocated by malloc(sizeof(Block)+totalSize) and deallocated by free(): this can be improved by allocating from aprivate heap instead
165  // Segments are allocated just after freeObjects, i.e. at ((uint8_t *)this)+sizeof(Block)
166  class Block
167  {
168  friend class Memory;
169  private:
170  private:
171  const uint16_t segmentCount;
172  const size_t segmentSize; // power of 2; includes the pointer to the block
173  const size_t totalSize; // segmentCount x segmentSize
174  Block *_next;
175  Block *_prev;
176  volatile int32_t freeSegments[2]; // stores the free segments per stack
177  void *operator new(size_t s, size_t objectSize, uint16_t objectCount);
178  void operator delete(void *b);
179  Block(size_t segmentSize, uint16_t segmentCount);
180  ~Block();
181  uint8_t *segments;
182  };
183  Block *firstBlock;
184  Block *lastBlock;
185 
186  // A Memory instance maintains two stacks, the alloc stack and the dealloc stack, both holding free segments
187  // alloc() pops a segment out of the alloc stack, while dealloc() pushes a segment on top of the dealloc stack
188  // When the alloc stack is empty, alloc() tries to dealocate an empty block if any, and decreases the dealloc stack;
189  // then the two stacks are swapped: the dealloc stack becomes the alloc stack and vice-versa
190  // If the dealloc stack is not full enough, no swapping is performed, but a new block is allocated instead and the alloc stack refilled
191  // When the dealloc stack is full, dealloc() swaps the stack pointers if the alloc stack is empty enough
192  // If that's not the case, it tries to deallocate an empty block, if any, and if unsuccessful, the dealloc stack is increased (realloc)
193  // Synchronization between multiple alloc() is lock-free under no contention (alloc_top) and uses a lock under contention (a_sem); idem for dealloc() (resp. dealloc_top and d_sem)
194  // Synchronization between one alloc() swapping stacks and multiple dealloc() is lock-free under no contention (a_d_guard), and uses a lock (a_d_sem) under contention
195  // Synchronization between one dealloc() swapping stacks and multiple alloc() is lock-free under no contention (d_a_guard), and uses a lock (d_a_sem) under contention
196  class Stack
197  {
198  public:
199  uint8_t **stack; // points to segments
200  int32_t top;
201  int32_t size; // in ints
202  uint32_t id; // used to retrieve a block's free segments per stack
203  };
204  Stack stacks[2];
205  Stack *volatile alloc_stack;
206  Stack *volatile dealloc_stack;
207  Semaphore *a_sem; // synchronizes alloc threads
208  Semaphore *d_sem; // synchronizes dealloc threads
209  Semaphore *a_d_sem; // synchronizes one alloc thread and multiple dealloc threads using the dealloc stack
210  Semaphore *d_a_sem; // synchronizes one dealloc thread and multiple alloc threads using the alloc stack
211  int32_t volatile a_d_guard;
212  int32_t volatile d_a_guard;
213  int32_t volatile alloc_top; // avoids contention on alloc_stack->top
214  int32_t volatile dealloc_top; // avoids contention on dealloc_stack->top
215 
216  void *allocSegment(int32_t location) const;
217  void deallocSegment(void *o, int32_t location) const;
218  bool deallocBlock(); // attempt to find an empty bloc and deallocate it and shrink the dealloc stack; return true is succeeded
219  void swapStackPointers();
220 
221  const size_t objectSize;
222  Memory(size_t objectSize);
223  void *operator new(size_t s, uint16_t index);
224  void operator delete(void *b);
225  static size_t GetNormalizedSize(size_t s, uint8_t &pow2); // converts a size into the next power of 2
226 public:
227  static Memory *GetStatic(size_t s); // called at class loading time; sequential calls
228  static Memory *GetDynamic(size_t s); // called dynamically (rwa storage); concurrent calls
229  Memory(); // do NOT use
230  ~Memory();
231  const uint32_t getObjectSize() const;
232  void *alloc();
233  void *alloc(uint32_t &normalizedSize); // same as alloc; returns the allocated size as a power of 2
234  void dealloc(void *o);
235 };
236 #elif defined MEMORY_MALLOC
237 // for testing only!
238 class mBrane_dll Memory
239 {
240 private:
241  const size_t objectSize;
242  Memory(size_t objectSize): objectSize(objectSize) {}
243 public:
244  static Memory *GetStatic(size_t s)
245  {
246  return new Memory(s); // memory leak: Memory(s) never deallocated
247  }
248  static Memory *GetDynamic(size_t s)
249  {
250  return new Memory(s); // idem
251  }
252  ~Memory() {}
253  const uint32_t getObjectSize() const
254  {
255  return objectSize;
256  }
257  void *alloc()
258  {
259  return malloc(objectSize);
260  }
261  void *alloc(uint32_t &normalizedSize)
262  {
263  normalizedSize = objectSize;
264  return malloc(objectSize);
265  }
266  void dealloc(void *o)
267  {
268  free(o);
269  }
270 };
271 #endif
272 }
273 }
274 
275 
276 #endif
Block * lastBlock
Definition: memory.h:134
Definition: utils.h:167
static std::mutex s_mutex
Definition: memory.h:105
const size_t totalSize
Definition: memory.h:121
const uint16_t objectCount
Definition: memory.h:118
std::mutex m_mutex
Definition: memory.h:137
Definition: array.h:84
Block * _next
Definition: memory.h:122
static Array< Memory, 16 > * Memories
Definition: memory.h:104
Block * emptyBlock
Definition: memory.h:135
Definition: array.h:107
uint16_t freeObjects
Definition: memory.h:119
Definition: utils.h:199
Block * firstBlock
Definition: memory.h:133
uint32_t freeObjects
Definition: memory.h:136
const size_t objectSize
Definition: memory.h:120
Definition: array.h:162
const size_t objectSize
Definition: memory.h:132
Definition: memory.h:101
Block * _prev
Definition: memory.h:123
uint8_t * firstFree
Definition: memory.h:124
Definition: memory.h:114