KiCad PCB EDA Suite
cached_container.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright 2013-2017 CERN
5  * @author Maciej Suminski <maciej.suminski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
34 #include <gal/opengl/vertex_item.h>
35 #include <gal/opengl/utils.h>
36 
37 #include <list>
38 #include <cassert>
39 
40 #ifdef __WXDEBUG__
41 #include <wx/log.h>
42 #include <profile.h>
43 #endif /* __WXDEBUG__ */
44 
45 using namespace KIGFX;
46 
47 CACHED_CONTAINER::CACHED_CONTAINER( unsigned int aSize ) :
48  VERTEX_CONTAINER( aSize ), m_item( NULL ), m_chunkSize( 0 ), m_chunkOffset( 0 ), m_maxIndex( 0 )
49 {
50  // In the beginning there is only free space
51  m_freeChunks.insert( std::make_pair( aSize, 0 ) );
52 }
53 
54 
56 {
57  assert( aItem != NULL );
58 
59  unsigned int itemSize = aItem->GetSize();
60  m_item = aItem;
61  m_chunkSize = itemSize;
62 
63  // Get the previously set offset if the item was stored previously
64  m_chunkOffset = itemSize > 0 ? aItem->GetOffset() : -1;
65 
66 #if CACHED_CONTAINER_TEST > 1
67  wxLogDebug( wxT( "Adding/editing item 0x%08lx (size %d)" ), (long) m_item, itemSize );
68 #endif
69 }
70 
71 
73 {
74  assert( m_item != NULL );
75 
76  unsigned int itemSize = m_item->GetSize();
77 
78  // Finishing the previously edited item
79  if( itemSize < m_chunkSize )
80  {
81  // There is some not used but reserved memory left, so we should return it to the pool
82  int itemOffset = m_item->GetOffset();
83 
84  // Add the not used memory back to the pool
85  addFreeChunk( itemOffset + itemSize, m_chunkSize - itemSize );
86  // mergeFreeChunks(); // veery slow and buggy
87 
88  m_maxIndex = std::max( itemOffset + itemSize, m_maxIndex );
89  }
90 
91  if( itemSize > 0 )
92  m_items.insert( m_item );
93 
94  m_item = NULL;
95  m_chunkSize = 0;
96  m_chunkOffset = 0;
97 
98 #if CACHED_CONTAINER_TEST > 1
99  wxLogDebug( wxT( "Finishing item 0x%08lx (size %d)" ), (long) m_item, itemSize );
100  test();
101 #endif
102 }
103 
104 
105 VERTEX* CACHED_CONTAINER::Allocate( unsigned int aSize )
106 {
107  assert( m_item != NULL );
108  assert( IsMapped() );
109 
110  if( m_failed )
111  return NULL;
112 
113  unsigned int itemSize = m_item->GetSize();
114  unsigned int newSize = itemSize + aSize;
115 
116  if( newSize > m_chunkSize )
117  {
118  // There is not enough space in the currently reserved chunk, so we have to resize it
119  if( !reallocate( newSize ) )
120  {
121  m_failed = true;
122  return NULL;
123  }
124  }
125 
126  VERTEX* reserved = &m_vertices[m_chunkOffset + itemSize];
127 
128  // Now the item officially possesses the memory chunk
129  m_item->setSize( newSize );
130 
131  // The content has to be updated
132  m_dirty = true;
133 
134 #if CACHED_CONTAINER_TEST > 0
135  test();
136 #endif
137 #if CACHED_CONTAINER_TEST > 2
138  showFreeChunks();
139  showUsedChunks();
140 #endif
141 
142  return reserved;
143 }
144 
145 
147 {
148  assert( aItem != NULL );
149  assert( m_items.find( aItem ) != m_items.end() || aItem->GetSize() == 0 );
150 
151  int size = aItem->GetSize();
152 
153  if( size == 0 )
154  return; // Item is not stored here
155 
156  int offset = aItem->GetOffset();
157 
158 #if CACHED_CONTAINER_TEST > 1
159  wxLogDebug( wxT( "Removing 0x%08lx (size %d offset %d)" ), (long) aItem, size, offset );
160 #endif
161 
162  // Insert a free memory chunk entry in the place where item was stored
163  addFreeChunk( offset, size );
164 
165  // Indicate that the item is not stored in the container anymore
166  aItem->setSize( 0 );
167 
168  m_items.erase( aItem );
169 
170 #if CACHED_CONTAINER_TEST > 0
171  test();
172 #endif
173 
174  // This dynamic memory freeing optimize memory usage, but in fact can create
175  // out of memory issues because freeing and reallocation large chunks of memory
176  // can create memory fragmentation and no room to reallocate large chunks
177  // after many free/reallocate cycles during a session using the same complex board
178  // So it can be disable.
179  // Currently: it is disable to avoid "out of memory" issues
180 #if 0
181  // Dynamic memory freeing, there is no point in holding
182  // a large amount of memory when there is no use for it
183  if( m_freeSpace > ( 0.75 * m_currentSize ) && m_currentSize > m_initialSize )
184  {
186  }
187 #endif
188 }
189 
190 
192 {
194  m_maxIndex = 0;
195  m_failed = false;
196 
197  // Set the size of all the stored VERTEX_ITEMs to 0, so it is clear that they are not held
198  // in the container anymore
199  for( ITEMS::iterator it = m_items.begin(); it != m_items.end(); ++it )
200  ( *it )->setSize( 0 );
201 
202  m_items.clear();
203 
204  // Now there is only free space left
205  m_freeChunks.clear();
206  m_freeChunks.insert( std::make_pair( m_freeSpace, 0 ) );
207 }
208 
209 
210 bool CACHED_CONTAINER::reallocate( unsigned int aSize )
211 {
212  assert( aSize > 0 );
213  assert( IsMapped() );
214 
215  unsigned int itemSize = m_item->GetSize();
216 
217 #if CACHED_CONTAINER_TEST > 2
218  wxLogDebug( wxT( "Resize %p from %d to %d" ), m_item, itemSize, aSize );
219 #endif
220 
221  // Find a free space chunk >= aSize
222  FREE_CHUNK_MAP::iterator newChunk = m_freeChunks.lower_bound( aSize );
223 
224  // Is there enough space to store vertices?
225  if( newChunk == m_freeChunks.end() )
226  {
227  bool result;
228 
229  // Would it be enough to double the current space?
230  if( aSize < m_freeSpace + m_currentSize )
231  {
232  // Yes: exponential growing
233  result = defragmentResize( m_currentSize * 2 );
234  }
235  else
236  {
237  // No: grow to the nearest greater power of 2
238  result = defragmentResize( pow( 2, ceil( log2( m_currentSize * 2 + aSize ) ) ) );
239  }
240 
241  if( !result )
242  return false;
243 
244  newChunk = m_freeChunks.lower_bound( aSize );
245  assert( newChunk != m_freeChunks.end() );
246  }
247 
248  // Parameters of the allocated chunk
249  unsigned int newChunkSize = getChunkSize( *newChunk );
250  unsigned int newChunkOffset = getChunkOffset( *newChunk );
251 
252  assert( newChunkSize >= aSize );
253  assert( newChunkOffset < m_currentSize );
254 
255  // Check if the item was previously stored in the container
256  if( itemSize > 0 )
257  {
258 #if CACHED_CONTAINER_TEST > 3
259  wxLogDebug( wxT( "Moving 0x%08x from 0x%08x to 0x%08x" ),
260  (int) m_item, oldChunkOffset, newChunkOffset );
261 #endif
262  // The item was reallocated, so we have to copy all the old data to the new place
263  memcpy( &m_vertices[newChunkOffset], &m_vertices[m_chunkOffset], itemSize * VERTEX_SIZE );
264 
265  // Free the space used by the previous chunk
267  }
268 
269  // Remove the new allocated chunk from the free space pool
270  m_freeChunks.erase( newChunk );
271  m_freeSpace -= newChunkSize;
272 
273  m_chunkSize = newChunkSize;
274  m_chunkOffset = newChunkOffset;
275 
277 
278  return true;
279 }
280 
281 
283 {
284  // Defragmentation
285  ITEMS::iterator it, it_end;
286  int newOffset = 0;
287 
288  for( VERTEX_ITEM* item : m_items )
289  {
290  int itemOffset = item->GetOffset();
291  int itemSize = item->GetSize();
292 
293  // Move an item to the new container
294  memcpy( &aTarget[newOffset], &m_vertices[itemOffset], itemSize * VERTEX_SIZE );
295 
296  // Update new offset
297  item->setOffset( newOffset );
298 
299  // Move to the next free space
300  newOffset += itemSize;
301  }
302 
303  // Move the current item and place it at the end
304  if( m_item->GetSize() > 0 )
305  {
306  memcpy( &aTarget[newOffset], &m_vertices[m_item->GetOffset()],
307  m_item->GetSize() * VERTEX_SIZE );
308  m_item->setOffset( newOffset );
309  m_chunkOffset = newOffset;
310  }
311 
312  m_maxIndex = usedSpace();
313 }
314 
315 
317 {
318  if( m_freeChunks.size() <= 1 ) // There are no chunks that can be merged
319  return;
320 
321 #ifdef __WXDEBUG__
322  PROF_COUNTER totalTime;
323 #endif /* __WXDEBUG__ */
324 
325  // Reversed free chunks map - this one stores chunk size with its offset as the key
326  std::list<CHUNK> freeChunks;
327 
328  FREE_CHUNK_MAP::const_iterator it, it_end;
329 
330  for( it = m_freeChunks.begin(), it_end = m_freeChunks.end(); it != it_end; ++it )
331  {
332  freeChunks.emplace_back( it->second, it->first );
333  }
334 
335  m_freeChunks.clear();
336  freeChunks.sort();
337 
338  std::list<CHUNK>::const_iterator itf, itf_end;
339  unsigned int offset = freeChunks.front().first;
340  unsigned int size = freeChunks.front().second;
341  freeChunks.pop_front();
342 
343  for( itf = freeChunks.begin(), itf_end = freeChunks.end(); itf != itf_end; ++itf )
344  {
345  if( itf->first == offset + size )
346  {
347  // These chunks can be merged, so just increase the current chunk size and go on
348  size += itf->second;
349  }
350  else
351  {
352  // These chunks cannot be merged
353  // So store the previous one
354  m_freeChunks.insert( std::make_pair( size, offset ) );
355  // and let's check the next chunk
356  offset = itf->first;
357  size = itf->second;
358 
359  }
360  }
361 
362  // Add the last one
363  m_freeChunks.insert( std::make_pair( size, offset ) );
364 
365 #ifdef __WXDEBUG__
366  totalTime.Stop();
367  wxLogDebug( "Merged free chunks / %.1f ms", totalTime.msecs() );
368 #endif /* __WXDEBUG__ */
369 #if CACHED_CONTAINER_TEST > 0
370  test();
371 #endif
372 }
373 
374 
375 void CACHED_CONTAINER::addFreeChunk( unsigned int aOffset, unsigned int aSize )
376 {
377  assert( aOffset + aSize <= m_currentSize );
378  assert( aSize > 0 );
379 
380  m_freeChunks.insert( std::make_pair( aSize, aOffset ) );
381  m_freeSpace += aSize;
382 }
383 
384 
386 {
387 #ifdef __WXDEBUG__
388  FREE_CHUNK_MAP::iterator it;
389 
390  wxLogDebug( wxT( "Free chunks:" ) );
391 
392  for( it = m_freeChunks.begin(); it != m_freeChunks.end(); ++it )
393  {
394  unsigned int offset = getChunkOffset( *it );
395  unsigned int size = getChunkSize( *it );
396  assert( size > 0 );
397 
398  wxLogDebug( wxT( "[0x%08x-0x%08x] (size %d)" ),
399  offset, offset + size - 1, size );
400  }
401 #endif /* __WXDEBUG__ */
402 }
403 
404 
406 {
407 #ifdef __WXDEBUG__
408  ITEMS::iterator it;
409 
410  wxLogDebug( wxT( "Used chunks:" ) );
411 
412  for( it = m_items.begin(); it != m_items.end(); ++it )
413  {
414  VERTEX_ITEM* item = *it;
415  unsigned int offset = item->GetOffset();
416  unsigned int size = item->GetSize();
417  assert( size > 0 );
418 
419  wxLogDebug( wxT( "[0x%08x-0x%08x] @ 0x%p (size %d)" ),
420  offset, offset + size - 1, item, size );
421  }
422 #endif /* __WXDEBUG__ */
423 }
424 
425 
427 {
428 #ifdef __WXDEBUG__
429  // Free space check
430  unsigned int freeSpace = 0;
431  FREE_CHUNK_MAP::iterator itf;
432 
433  for( itf = m_freeChunks.begin(); itf != m_freeChunks.end(); ++itf )
434  freeSpace += getChunkSize( *itf );
435 
436  assert( freeSpace == m_freeSpace );
437 
438  // Used space check
439  unsigned int used_space = 0;
440  ITEMS::iterator itr;
441  for( itr = m_items.begin(); itr != m_items.end(); ++itr )
442  used_space += ( *itr )->GetSize();
443 
444  // If we have a chunk assigned, then there must be an item edited
445  assert( m_chunkSize == 0 || m_item );
446 
447  // Currently reserved chunk is also counted as used
448  used_space += m_chunkSize;
449 
450  assert( ( m_freeSpace + used_space ) == m_currentSize );
451 
452  // Overlapping check TODO
453 #endif /* __WXDEBUG__ */
454 }
void Stop()
save the time when this function was called, and set the counter stane to stop
Definition: profile.h:82
unsigned int m_initialSize
Store the initial size, so it can be resized to this on Clear()
void showFreeChunks()
Debug & test functions.
void addFreeChunk(unsigned int aOffset, unsigned int aSize)
Adds a chunk marked as a free space.
Class CAIRO_GAL is the cairo implementation of the graphics abstraction layer.
Definition: color4d.cpp:131
Data structure for vertices {X,Y,Z,R,G,B,A,shader&param}
Definition: vertex_common.h:56
double msecs(bool aSinceLast=false)
Definition: profile.h:143
unsigned int GetSize() const
Function GetSize() Returns information about number of vertices stored.
Definition: vertex_item.h:56
unsigned int getChunkOffset(const CHUNK &aChunk) const
Returns the offset of a chunk.
Class to control vertex container and GPU with possibility of emulating old-style OpenGL 1....
void defragment(VERTEX *aTarget)
Transfers all stored data to a new buffer, removing empty spaces between the data chunks in the conta...
unsigned int m_currentSize
Current container size, expressed in vertices
unsigned int m_chunkSize
Properties of currently modified chunk & item
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:44
virtual void SetItem(VERTEX_ITEM *aItem) override
VERTEX * m_vertices
Actual storage memory
void setSize(unsigned int aSize)
Function SetSize() Sets data size in the container.
Definition: vertex_item.h:97
ITEMS m_items
Stored VERTEX_ITEMs
VERTEX_ITEM * m_item
Currently modified item
#define NULL
virtual void FinishItem() override
unsigned int m_freeSpace
Free space left in the container, expressed in vertices
int getChunkSize(const CHUNK &aChunk) const
Returns the size of a chunk.
void setOffset(unsigned int aOffset)
Function SetOffset() Sets data offset in the container.
Definition: vertex_item.h:87
void mergeFreeChunks()
Looks for consecutive free memory chunks and merges them, decreasing fragmentation of memory.
virtual void Clear() override
virtual VERTEX * Allocate(unsigned int aSize) override
FREE_CHUNK_MAP m_freeChunks
Stores size & offset of free chunks.
CACHED_CONTAINER(unsigned int aSize=DEFAULT_SIZE)
bool reallocate(unsigned int aSize)
Resizes the chunk that stores the current item to the given size.
unsigned int usedSpace() const
Function usedSpace() returns size of the used memory space.
Class to handle an item held in a container.
static constexpr size_t VERTEX_SIZE
Definition: vertex_common.h:63
unsigned int GetOffset() const
Function GetOffset() Returns data offset in the container.
Definition: vertex_item.h:66
unsigned int m_maxIndex
Maximal vertex index number stored in the container
virtual bool IsMapped() const =0
Returns true if vertex buffer is currently mapped.
virtual void Delete(VERTEX_ITEM *aItem) override
virtual bool defragmentResize(unsigned int aNewSize)=0
Removes empty spaces between chunks and optionally resizes the container.