`Triangles::clear ()` use-after-free

[shamefulCake1]

The clear() method looks like this:

void
Triangles::clear ()
{
  m_edges_heap.clear ();
  mp_triangles.clear ();
  m_vertex_heap.clear ();
  m_returned_edges.clear ();
  m_is_constrained = false;
  m_level = 0;
  m_id = 0;
}

However, mp_triangles contains pointers to objects stored in m_edges_heap, so running mp_triangles.clear (); after m_edges_heap.clear (); makes it "examine" objects that have already been free-ed in m_edges_heap.clear ();, which is a use-after-free.

As a "simple fix" I have come up with is just exchanging the two calls to clear().

@@ -1414,8 +1414,8 @@ Triangles::remove_outside_triangles ()
 void
 Triangles::clear ()
 {
-  m_edges_heap.clear ();
   mp_triangles.clear ();
+  m_edges_heap.clear ();
   m_vertex_heap.clear ();
   m_returned_edges.clear ();
   m_is_constrained = false;

but maybe my logic is wrong?

Overall it does not sound like a good practice, to have seemingly unrelated calls depend on the sequence. Something RAII-like would have been much nicer.

This is indicated by the test called dbTrianglesTests:triangulate_basic.

[klayoutmatthias]

Thanks, you're right.

The heap memory management model is inherently susceptible to such problems, but it is fast and lean to implement. RAII is also depending in the order (of initialization), so it is not necessarily safer. In the destructor there is an explicit cleanup before the heaps are destroyed implicitly. That is already in the proper order.

A safe way are smart pointers. They would eliminate the need for heaps, but they come with considerable overhead.

I think changing the order is good enough. I'll add a comment indicating that.

A general question: you are not the only person trying to sanitize the code. I appreciate that, but I'd prefer there was only one activity towards that. Otherwise the result will be a flood of issue reports and conflicts I have to resolve on my side. Are you acting in the name of some entity? If so, let me know (if needed through a private channel), so there is some chance for a coordinated action.

Matthias

[shamefulCake1]

RAII and smart pointers overlap quite a lot. And, as far as I remember, std::unique_ptr has more or less the same performance as a bare pointer plus-minus the "new/delete" fee, which is hard to avoid even with manual memory management, unless a sophisticated memory manager is implemented.

No, I am not representing any entity.

[klayoutmatthias]

std::unique_ptr is indeed lightweight and uses RAII. But that is a very simple and not very smart pointer and you cannot share it. It makes sense if the object holder is also the object user. But that is not something you can use for a graph.

I am talking std::shared_ptr and std::weak_ptr which need add management overhead. Like there needs to be some management object that the weak pointers can refer to even if the original object gets destroyed. Also, the type-agnostic implementation of STL makes it very difficult to use IMHO.

Matthias

[shamefulCake1]

I can't say that I have a huge experience on this, but generally I tried to have a single owner with a unique_ptr, and "visitors" visiting the object with references or pointers-to-const. Mutation would have to happen through the owner, of course.

But I am not familiar with KLayout's architecture, it is very possible that what I am used to is inapplicable to KLayout.

Meanwhile, if exchanging the calls to "close" is good enough, can I close the issue?

[klayoutmatthias]

In that case, the edges and triangles form a graph: a triangle is enclosed by three edges and has three pointers to edges therefore. The edges have up to two pointers to triangles. Triangles are not owners of edges and vice versa. Instead the heaps are owners. They are basically smart pointers (that is why clear() deletes the objects). But the pointers inside the triangles still persist and that is why you see the memory issue with the wrong order of destruction. So this is equivalent to using unique_ptr and still keeping normal pointers elsewhere. There is an inherent risk for memory corruption, as we see here.

A clean way to solve that are weak-pointers: if the triangles had weak instead of normal pointers for the edges, they could know if the edges are destroyed and not access the edges then.

But anyway, I think this is a marginal issue and of course, the bug needs to be fixed. Please leave the ticket open, please. I'll close it once the code is changed.

Matthias

[Kazzz-S]

Hi Matthias,

I'm modifying the macOS build system so that the debug build uses ASAN (Address SANitizer) for clang++.
The attached ZIP file contains three log files (see the table below) of the ut_runner program.
GitHub1757.zip

Srl.No.	Log File	Build (1)	ASAN	ut_runner --exclude	Remarks
1	No1-QATest_*.macQAT.log	debug	enabled	nil	ut_runner aborted (2) reason
2	No2-QATest_*.macQAT.log	release	disabled	nil	ut_runner went through
3	No3-QATest_*.macQAT.log	debug	enabled	dbTrianglesTests	ut_runner went through

(1) % ./build4mac.py -q qt5macports -r sys -p sys [--debug]
(2) Running dbTrianglesTests:triangulate_basic
==67539==ERROR: AddressSanitizer: heap-use-after-free

I think the No1-QATest_*.macQAT.log file captured this problem.

Regards,
Kazzz-S

[klayoutmatthias]

Hi @Kazzz-S,

good thing is, I did not spot anything else :)

There is some noise about "TSDDtor" which I understand is only telling me that thread-local data has been freed. Plus some other log events that seem to be related to sub-processes.

But I wonder why ASAN did not capture the original problem in all logs. Basically there is no specific test for clear and the problem addressed in the issue. I think therefore that ASAN is still working and it is good to see it does not report further issues.

I tried with valgrind and found an uninitialized value in addition (m_id of db::Triangles). That is not a functional issue as the exact value does not matter, but I will fix it too.

Thanks and best regards,

Matthias

[shamefulCake1]

I used clang++ 17.0.6 to compile klayout with asan, and the only change I actually made is like this:

diff --git a/src/klayout.pri b/src/klayout.pri
index a370e8490..56cda0e02 100644
--- a/src/klayout.pri
+++ b/src/klayout.pri
@@ -94,6 +94,12 @@ equals(HAVE_EXPAT, "1") {
   DEFINES += HAVE_EXPAT
 } 
+QMAKE_CXXFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-optimize-sibling-calls -Wsign-conversion -Wall -Wextra -Wpedantic -Wconversion
+QMAKE_LFLAGS   += -fsanitize=address

Nothing more.

[Kazzz-S]

My setting is as follows.

diff --git a/src/klayout.pri b/src/klayout.pri
index a370e8490..dd882e4c1 100644
--- a/src/klayout.pri
+++ b/src/klayout.pri
@@ -118,6 +118,15 @@ equals(HAVE_GIT2, "1") {
   DEFINES += HAVE_GIT2
 }

+# Use the Address Sanitizer for the debug build on Mac
+mac {
+  USE_ASAN_MAC = $$system(echo $$(MAC_USE_ASAN))
+  equals(USE_ASAN_MAC, "1") {
+    QMAKE_CXXFLAGS += -fsanitize=address
+    QMAKE_LFLAGS += -fsanitize=address
+  }
+}
+
 equals(HAVE_RUBY, "1") {
   !isEmpty(BITS_PATH) {
     include($$BITS_PATH/ruby/ruby.pri)

Only in the debug build, build4mac.py sets MAC_USE_ASAN="1" and links against ASAN.
Then, ut_runner was invoked with

export MallocNanoZone="0"
export ASAN_OPTIONS="ast_unwind_on_malloc=0:verbosity=1:detect_leaks=0:abort_on_error=0:halt_on_error=0:symbolize=1"