Why:
As is evident from BUG 395624, we do have an issue with memory safety
in KPatience. However, debugging it is really hard, and it is hard to
find out the root cause.
To ease further debugging, simplifying and modernizing the memory
management seemed to be of utmost importance.
State before this patch:
- The TREE datastructure was used to store the state after a specific move. However, you would not know that by looking at it, as it only had a depth, left and right member. The actual data was always stored directly after it (as an array of PileBytes bytes). TREE actual data ------------------=-------------------- |depth|left|right|=Pile1|Pile2|Pile3... ------------------=-------------------- ^ ^ | |----was accesed via p+(sizeof(TREE)) | pointer p to here gets returned
- The memory manager used a bump allocator which was used for both the POSITION and TREE structs. The bumb allocator used a simple linked list of blocks, which contained an array of data. The contents of that array looked like --------------------------------------------------------------------- |TREE1|Tree1Data|Tree2|Tree2Data |POSITION|TREE3|TREE3DATA|... ---------------------------------------------------------------------
- To decide how much memory needs to be allocated, the size of the required memory was passed to the MemoryManager at runtime.
- (De)allocations were made with C functions, so neither ctors nor dtors were called.
- The MemoryManager stored and accessed state in static variables. Those were partially set by the concrete Solver instance on initialization.
State after this patch:
- The MemoryManager, the TREE and datastructures involving TREE take PileBytes as a template argument. TREE has been renamed to TTree (templated tree), mostly to make finding usages easier.
- As the TTree now knows how much data it has to store, it has an actual data member. Furthermore, in debug builds there is a canary value afterwards, which can be used to check for out-of-bound writes. ------------------------------------------------ |depth|left|right|data [PileBytes large]|CANARY| ------------------------------------------------ {--------------always there------------}={in debug bulids}
- As the information is passed via template parameters, the static variables used for communicating sizes could be removed.
- The bump allocator has been splitted, in one for TTrees and one for POSITIONs. They still share the total allocation limit. Splitting the allocator also allowdes for a now even simple bump allocator. It uses a simple array, and just returns a pointer to array[fill] upon request. If the array runs out of space, a new block gets allocated, just as before.
- The blocks of the bump allocator now use unique_ptr, instead of having to manually release the memory at the end.
- No code outside of the core memory allocation has been altered.
Downsides:
- There is a somewhat larger initial memory footprint, as we are allocating a block for both POSITIONs and TTreees. However, in actual usage that should not matter, as the solver normally needs quite a lot of both of them, and would allocate a new block anyway.
- The new bump allocator contains an array, which means that for each member the constructor gets called (previously the data was just memzeroed). However, except for debug builds, the constructors of TTree and POSITION are trivial, so there shouldn't be any work done.
- (De)Allocations are now done with new and delete to ensure that ctors and dtors run.
- All those templates aren't great for readability.
Testing:- Only manual testing to check whether the solver
- The existing unit tests partially fail, but did so already before this change.
- Application was run under sanitizers to check for new memory issues; none were found so far.