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