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