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 chuncks of memory
176  // can create memory fragmentation and no room to reallocate large chuncks
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
266  addFreeChunk( m_chunkOffset, m_chunkSize );
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.push_back( std::make_pair( 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 usedSpace() const
Function usedSpace() returns size of the used memory space.
unsigned int m_initialSize
Store the initial size, so it can be resized to this on Clear()
void showFreeChunks()
Debug & test functions.
int getChunkSize(const CHUNK &aChunk) const
Returns the size of a chunk.
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: class_module.h:58
Data structure for vertices {X,Y,Z,R,G,B,A,shader¶m}
Definition: vertex_common.h:50
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:45
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
virtual void FinishItem() override
>
unsigned int m_freeSpace
Free space left in the container, expressed in vertices
unsigned int getChunkOffset(const CHUNK &aChunk) const
Returns the offset 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
>
unsigned int GetOffset() const
Function GetOffset() Returns data offset in the container.
Definition: vertex_item.h:66
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)
double msecs() const
Definition: profile.h:124
bool reallocate(unsigned int aSize)
Resizes the chunk that stores the current item to the given size.
#define max(a, b)
Definition: auxiliary.h:86
Class to handle an item held in a container.
static constexpr size_t VERTEX_SIZE
Definition: vertex_common.h:57
unsigned int GetSize() const
Function GetSize() Returns information about number of vertices stored.
Definition: vertex_item.h:56
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.