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 )
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 
89  if( itemSize > 0 )
90  m_items.insert( m_item );
91 
92  m_item = NULL;
93  m_chunkSize = 0;
94  m_chunkOffset = 0;
95 
96 #if CACHED_CONTAINER_TEST > 1
97  wxLogDebug( wxT( "Finishing item 0x%08lx (size %d)" ), (long) m_item, itemSize );
98  test();
99 #endif
100 }
101 
102 
103 VERTEX* CACHED_CONTAINER::Allocate( unsigned int aSize )
104 {
105  assert( m_item != NULL );
106  assert( IsMapped() );
107 
108  if( m_failed )
109  return NULL;
110 
111  unsigned int itemSize = m_item->GetSize();
112  unsigned int newSize = itemSize + aSize;
113 
114  if( newSize > m_chunkSize )
115  {
116  // There is not enough space in the currently reserved chunk, so we have to resize it
117  if( !reallocate( newSize ) )
118  {
119  m_failed = true;
120  return NULL;
121  }
122  }
123 
124  VERTEX* reserved = &m_vertices[m_chunkOffset + itemSize];
125 
126  // Now the item officially possesses the memory chunk
127  m_item->setSize( newSize );
128 
129  // The content has to be updated
130  m_dirty = true;
131 
132 #if CACHED_CONTAINER_TEST > 0
133  test();
134 #endif
135 #if CACHED_CONTAINER_TEST > 2
136  showFreeChunks();
137  showUsedChunks();
138 #endif
139 
140  return reserved;
141 }
142 
143 
145 {
146  assert( aItem != NULL );
147  assert( m_items.find( aItem ) != m_items.end() || aItem->GetSize() == 0 );
148 
149  int size = aItem->GetSize();
150 
151  if( size == 0 )
152  return; // Item is not stored here
153 
154  int offset = aItem->GetOffset();
155 
156 #if CACHED_CONTAINER_TEST > 1
157  wxLogDebug( wxT( "Removing 0x%08lx (size %d offset %d)" ), (long) aItem, size, offset );
158 #endif
159 
160  // Insert a free memory chunk entry in the place where item was stored
161  addFreeChunk( offset, size );
162 
163  // Indicate that the item is not stored in the container anymore
164  aItem->setSize( 0 );
165 
166  m_items.erase( aItem );
167 
168 #if CACHED_CONTAINER_TEST > 0
169  test();
170 #endif
171 
172  // This dynamic memory freeing optimize memory usage, but in fact can create
173  // out of memory issues because freeing and reallocation large chuncks of memory
174  // can create memory fragmentation and no room to reallocate large chuncks
175  // after many free/reallocate cycles during a session using the same complex board
176  // So it can be disable.
177  // Currently: it is disable to avoid "out of memory" issues
178 #if 0
179  // Dynamic memory freeing, there is no point in holding
180  // a large amount of memory when there is no use for it
181  if( m_freeSpace > ( 0.75 * m_currentSize ) && m_currentSize > m_initialSize )
182  {
184  }
185 #endif
186 }
187 
188 
190 {
192  m_failed = false;
193 
194  // Set the size of all the stored VERTEX_ITEMs to 0, so it is clear that they are not held
195  // in the container anymore
196  for( ITEMS::iterator it = m_items.begin(); it != m_items.end(); ++it )
197  ( *it )->setSize( 0 );
198 
199  m_items.clear();
200 
201  // Now there is only free space left
202  m_freeChunks.clear();
203  m_freeChunks.insert( std::make_pair( m_freeSpace, 0 ) );
204 }
205 
206 
207 bool CACHED_CONTAINER::reallocate( unsigned int aSize )
208 {
209  assert( aSize > 0 );
210  assert( IsMapped() );
211 
212  unsigned int itemSize = m_item->GetSize();
213 
214 #if CACHED_CONTAINER_TEST > 2
215  wxLogDebug( wxT( "Resize %p from %d to %d" ), m_item, itemSize, aSize );
216 #endif
217 
218  // Find a free space chunk >= aSize
219  FREE_CHUNK_MAP::iterator newChunk = m_freeChunks.lower_bound( aSize );
220 
221  // Is there enough space to store vertices?
222  if( newChunk == m_freeChunks.end() )
223  {
224  bool result;
225 
226  // Would it be enough to double the current space?
227  if( aSize < m_freeSpace + m_currentSize )
228  {
229  // Yes: exponential growing
230  result = defragmentResize( m_currentSize * 2 );
231  }
232  else
233  {
234  // No: grow to the nearest greater power of 2
235  result = defragmentResize( pow( 2, ceil( log2( m_currentSize * 2 + aSize ) ) ) );
236  }
237 
238  if( !result )
239  return false;
240 
241  newChunk = m_freeChunks.lower_bound( aSize );
242  assert( newChunk != m_freeChunks.end() );
243  }
244 
245  // Parameters of the allocated chunk
246  unsigned int newChunkSize = getChunkSize( *newChunk );
247  unsigned int newChunkOffset = getChunkOffset( *newChunk );
248 
249  assert( newChunkSize >= aSize );
250  assert( newChunkOffset < m_currentSize );
251 
252  // Check if the item was previously stored in the container
253  if( itemSize > 0 )
254  {
255 #if CACHED_CONTAINER_TEST > 3
256  wxLogDebug( wxT( "Moving 0x%08x from 0x%08x to 0x%08x" ),
257  (int) m_item, oldChunkOffset, newChunkOffset );
258 #endif
259  // The item was reallocated, so we have to copy all the old data to the new place
260  memcpy( &m_vertices[newChunkOffset], &m_vertices[m_chunkOffset], itemSize * VertexSize );
261 
262  // Free the space used by the previous chunk
263  addFreeChunk( m_chunkOffset, m_chunkSize );
264  }
265 
266  // Remove the new allocated chunk from the free space pool
267  m_freeChunks.erase( newChunk );
268  m_freeSpace -= newChunkSize;
269 
270  m_chunkSize = newChunkSize;
271  m_chunkOffset = newChunkOffset;
272 
274 
275  return true;
276 }
277 
278 
280 {
281  // Defragmentation
282  ITEMS::iterator it, it_end;
283  int newOffset = 0;
284 
285  for( VERTEX_ITEM* item : m_items )
286  {
287  int itemOffset = item->GetOffset();
288  int itemSize = item->GetSize();
289 
290  // Move an item to the new container
291  memcpy( &aTarget[newOffset], &m_vertices[itemOffset], itemSize * VertexSize );
292 
293  // Update new offset
294  item->setOffset( newOffset );
295 
296  // Move to the next free space
297  newOffset += itemSize;
298  }
299 
300  // Move the current item and place it at the end
301  if( m_item->GetSize() > 0 )
302  {
303  memcpy( &aTarget[newOffset], &m_vertices[m_item->GetOffset()],
304  m_item->GetSize() * VertexSize );
305  m_item->setOffset( newOffset );
306  m_chunkOffset = newOffset;
307  }
308 }
309 
310 
312 {
313  if( m_freeChunks.size() <= 1 ) // There are no chunks that can be merged
314  return;
315 
316 #ifdef __WXDEBUG__
317  PROF_COUNTER totalTime;
318 #endif /* __WXDEBUG__ */
319 
320  // Reversed free chunks map - this one stores chunk size with its offset as the key
321  std::list<CHUNK> freeChunks;
322 
323  FREE_CHUNK_MAP::const_iterator it, it_end;
324 
325  for( it = m_freeChunks.begin(), it_end = m_freeChunks.end(); it != it_end; ++it )
326  {
327  freeChunks.push_back( std::make_pair( it->second, it->first ) );
328  }
329 
330  m_freeChunks.clear();
331  freeChunks.sort();
332 
333  std::list<CHUNK>::const_iterator itf, itf_end;
334  unsigned int offset = freeChunks.front().first;
335  unsigned int size = freeChunks.front().second;
336  freeChunks.pop_front();
337 
338  for( itf = freeChunks.begin(), itf_end = freeChunks.end(); itf != itf_end; ++itf )
339  {
340  if( itf->first == offset + size )
341  {
342  // These chunks can be merged, so just increase the current chunk size and go on
343  size += itf->second;
344  }
345  else
346  {
347  // These chunks cannot be merged
348  // So store the previous one
349  m_freeChunks.insert( std::make_pair( size, offset ) );
350  // and let's check the next chunk
351  offset = itf->first;
352  size = itf->second;
353 
354  }
355  }
356 
357  // Add the last one
358  m_freeChunks.insert( std::make_pair( size, offset ) );
359 
360 #ifdef __WXDEBUG__
361  totalTime.Stop();
362  wxLogDebug( "Merged free chunks / %.1f ms", totalTime.msecs() );
363 #endif /* __WXDEBUG__ */
364 #if CACHED_CONTAINER_TEST > 0
365  test();
366 #endif
367 }
368 
369 
370 void CACHED_CONTAINER::addFreeChunk( unsigned int aOffset, unsigned int aSize )
371 {
372  assert( aOffset + aSize <= m_currentSize );
373  assert( aSize > 0 );
374 
375  m_freeChunks.insert( std::make_pair( aSize, aOffset ) );
376  m_freeSpace += aSize;
377 }
378 
379 
381 {
382 #ifdef __WXDEBUG__
383  FREE_CHUNK_MAP::iterator it;
384 
385  wxLogDebug( wxT( "Free chunks:" ) );
386 
387  for( it = m_freeChunks.begin(); it != m_freeChunks.end(); ++it )
388  {
389  unsigned int offset = getChunkOffset( *it );
390  unsigned int size = getChunkSize( *it );
391  assert( size > 0 );
392 
393  wxLogDebug( wxT( "[0x%08x-0x%08x] (size %d)" ),
394  offset, offset + size - 1, size );
395  }
396 #endif /* __WXDEBUG__ */
397 }
398 
399 
401 {
402 #ifdef __WXDEBUG__
403  ITEMS::iterator it;
404 
405  wxLogDebug( wxT( "Used chunks:" ) );
406 
407  for( it = m_items.begin(); it != m_items.end(); ++it )
408  {
409  VERTEX_ITEM* item = *it;
410  unsigned int offset = item->GetOffset();
411  unsigned int size = item->GetSize();
412  assert( size > 0 );
413 
414  wxLogDebug( wxT( "[0x%08x-0x%08x] @ 0x%p (size %d)" ),
415  offset, offset + size - 1, item, size );
416  }
417 #endif /* __WXDEBUG__ */
418 }
419 
420 
422 {
423 #ifdef __WXDEBUG__
424  // Free space check
425  unsigned int freeSpace = 0;
426  FREE_CHUNK_MAP::iterator itf;
427 
428  for( itf = m_freeChunks.begin(); itf != m_freeChunks.end(); ++itf )
429  freeSpace += getChunkSize( *itf );
430 
431  assert( freeSpace == m_freeSpace );
432 
433  // Used space check
434  unsigned int used_space = 0;
435  ITEMS::iterator itr;
436  for( itr = m_items.begin(); itr != m_items.end(); ++itr )
437  used_space += ( *itr )->GetSize();
438 
439  // If we have a chunk assigned, then there must be an item edited
440  assert( m_chunkSize == 0 || m_item );
441 
442  // Currently reserved chunk is also counted as used
443  used_space += m_chunkSize;
444 
445  assert( ( m_freeSpace + used_space ) == m_currentSize );
446 
447  // Overlapping check TODO
448 #endif /* __WXDEBUG__ */
449 }
const size_t VertexSize
Definition: vertex_common.h:57
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
Actual storage memory (should be handled using malloc/realloc/free to speed up resizing) ...
void showFreeChunks()
Debug & test functions.
int getChunkSize(const CHUNK &aChunk) const
Function getChunkSize() returns size of the given chunk.
void addFreeChunk(unsigned int aOffset, unsigned int aSize)
Function addFreeChunk Adds a chunk marked as free.
Class CAIRO_GAL is the cairo implementation of the graphics abstraction layer.
Definition: class_module.h:58
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
Store the initial size, so it can be resized to this on Clear()
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
State flags.
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
How big is the current container, expressed in vertices.
unsigned int getChunkOffset(const CHUNK &aChunk) const
Function getChunkOffset() returns offset of the chunk.
void setOffset(unsigned int aOffset)
Function SetOffset() Sets data offset in the container.
Definition: vertex_item.h:87
void mergeFreeChunks()
Function 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)
Function reallocate() resizes the chunk that stores the current item to the given size...
Class to handle an item held in a container.
unsigned int GetSize() const
Function GetSize() Returns information about number of vertices stored.
Definition: vertex_item.h:56
virtual bool IsMapped() const =0
Function IsMapped() returns true if vertex buffer is currently mapped.
virtual void Delete(VERTEX_ITEM *aItem) override
>
virtual bool defragmentResize(unsigned int aNewSize)=0
Function defragmentResize() removes empty spaces between chunks and optionally resizes the container...