How to Write an LLDB Plugin with Python: Customized Stepping Logic

In a previous post we saw an example of a new debugger command that can be added using the LLDB API.

Custom commands allow you to create custom logic for inspecting the state of the target program during a break. Custom stepping logic allows you to create customized logic to determine how to progress through the target program.

As an example we will create a custom step class, FindVar, that will step through a program until it finds a variable named r1.

The Plugin Code


import lldb

class FindVar:

  def __init__(self, thread_plan, dict):
    self.thread_plan = thread_plan
    self.start_frame = thread_plan.GetThread().GetFrameAtIndex(0)

  def explains_stop(self, event):
    res = self.thread_plan.GetThread().GetStopReason() == lldb.eStopReasonTrace
    return res

  def should_stop(self, event):

    frame = self.thread_plan.GetThread().GetFrameAtIndex(0)
    a_var = frame.FindVariable("r1")

    if not a_var.IsValid():
      print "Havent found r1 yet"
      return False
    else:
      print "Found r1!"
      self.thread_plan.SetPlanComplete(True)
      return True

  def should_step(self):
    return True

Code Explanation

The three crucial methods are explains_stop, should_stop, and should_step.

explains_stop

To understand explains_stop lets look at the output of an ordinary LLDB session. If you run an ordinary LLDB session tracking a program, say a.out, and create a breakpoint at the function main, then run the program you should see output like this:


bash-3.2$ lldb ./a.out
(lldb) target create "./a.out"
Current executable set to './a.out' (x86_64).
(lldb) breakpoint set --n main
Breakpoint 1: where = a.out`main + 23 at main.cpp:8, address = 0x0000000100000d77
(lldb) r

The code will hit main immediately and break, spitting out the following info:


Process 18492 launched: './a.out' (x86_64)
Process 18492 stopped
* thread #1: tid = 0x58329e, 0x0000000100000d77 a.out`main + 23 at
main.cpp:8,
queue = 'com.apple.main-thread',
stop reason = breakpoint 1.1

frame #0: 0x0000000100000d77 a.out`main + 23 at main.cpp:8

Notice the text of line 6: stop reason = breakpoint 1. 1. In LLDB every stop has a reason. When the debugger stops it calls each active thread plan's explains_stop method. The first one to return true is the stop reason.

LLDB supports several stop reasons, in the python API the supported stop reasons are:

eStopReasonBreakpoint
eStopReasonException
eStopReasonExec
eStopReasonInstrumentation
eStopReasonInvalid
eStopReasonNone
eStopReasonPlanComplete
eStopReasonSignal
eStopReasonThreadExiting
eStopReasonTrace
eStopReasonWatchpoint

Our example plugin is just supposed to step through the program, so it only explains the stop if the the stop reason is eStopReasonTrace.

should_stop

In the event that our plan does explain the stop we get to decide whether to return control to the user or continue execution. This decision is made by the should_stop method.

For our plugin we are trying to run the program until a variable named r1 is defined, so we search for a variable named r1 in the current frame. If it exists we return control to the user. If it does not exist we continue execution.

should_step

Once we have decided to continue execution our plan has two options. It can resume normal execution, or it can take one step. In our case we want to step through the program one instruction at a time until r1 is defined, so we always return True, saying that we want to take a single step and then stop again.

Using the plugin

To use this plugin we first need to create an executable to use as the target. In this example we will use a simple C++ program. First enter this code into a file named contrived.cpp:


#include "contrived.h"

int contrived_1(const int l, const int v, const int q, my_value my_v) {
int r1 = l - v;
int r2 = q*l;

if (my_v.useless) {
return r1 - r2;
} else {
return my_v.x + my_v.y + my_v.z - r1*r2;
}
}

Next create the corresponding contrived.h file:

struct my_value {
int x;
int y;
int z;

bool useless;
};

int contrived_1(const int l, const int v, const int q, my_value my_v);

Finally create a main.cpp file:


#include <iostream>

#include "contrived.h"

using namespace std;

int main() {
int x = 2;
int y = 4;
int z = 9;

bool useless = true;

my_value v{x, y, z, useless};
int k = contrived_1(3, 4, -12, v);

cout << k << endl;
}

With these files created compile them with:


clang++ -g -O0 -std=c++11 contrived.cpp main.cpp

This will create an executable, a.out. With a.out created we can debug it and use our plugin.

In the directory lldb_plugin run the commands:


bash-3.2$ lldb ./a.out
(lldb) target create "./a.out"
Current executable set to './a.out' (x86_64).
(lldb) breakpoint set --n main
Breakpoint 1: where = a.out`main + 23 at main.cpp:8, address = 0x0000000100000d77
(lldb) r
Process 18568 launched: './a.out' (x86_64)
Process 18568 stopped
* thread #1: tid = 0x58688d, 0x0000000100000d77 a.out`main + 23 at main.cpp:8, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100000d77 a.out`main + 23 at main.cpp:8
   5       using namespace std;
   6       
   7       int main() {
-> 8         int x = 2;
   9         int y = 4;
   10        int z = 9;
   11      
(lldb) command script import find_var.py
(lldb) thread step-scripted -C find_var.FindVar
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Havent found r1 yet
Found r1!
Process 18568 stopped
* thread #1: tid = 0x58688d, 0x0000000100000d00 a.out`contrived_1(l=9, v=16777216, q=1, my_v=(x = 4, y = 2, z = 1606417248, useless = true)) at contrived.cpp:3, queue = 'com.apple.main-thread', stop reason = Python thread plan implemented by class find_var.FindVar.
    frame #0: 0x0000000100000d00 a.out`contrived_1(l=9, v=16777216, q=1, my_v=(x = 4, y = 2, z = 1606417248, useless = true)) at contrived.cpp:3
   1       #include "contrived.h"
   2       
-> 3       int contrived_1(const int l, const int v, const int q, my_value my_v) {
   4         int r1 = l - v;
   5         int r2 = q*l;
   6       
   7         if (my_v.useless) {

 

How to Correct Winding Order Errors in a 3D Triangular Mesh

If you have been using computational geometry libraries for any amount of time you have probably had to deal with winding order errors. These insidious bugs occur when a mesh contains some triangles that are wound clockwise and some that are wound counterclockwise, and they can cause huge headaches for users of libraries like CGAL and VTK.

Finding winding order inconsistencies in adjacent triangles

It is important to understand that a mesh does not have a correct or incorrect winding order, but a mesh can have an inconsistent winding order. This occurs when some triangles in the mesh are clockwise and others are counterclockwise.

Consider a simple mesh with 5 vertices and 3 triangles:

Vertices = {1, 2, 3, 4, 5}

Triangles = { <1, 2, 3>, <2, 4, 3>, <4, 3, 5> }

The figure below shows this mesh, with arcs sweeping out the vertices of each triangle

 

windingorderpicture
A mesh with 5 vertices and 3 triangles. The winding orders are not consistent

As you can see in the figure the rightmost triangle has a different winding order from the other 2 triangles, so the mesh does not have consistent winding order.

So if there is no correct winding order, how is it possible to detect and correct a situation like the one shown above? The answer comes from the fact that if 2 triangles in a mesh are connected, but have an identical ordered edge, then they have opposite winding orders.

Using the edge rule stated above we can see that there is a winding inconsistency because the ordered edges of triangle 2 are:

{2, 4}, {4, 3}, {3, 2}

And the ordered edges of triangle 3 are:

{5, 4}, {4, 3}, and {3, 5}

The ordered edge {4, 3} is common to both, so the 2 triangles have a winding order conflict, which is seen in the picture. The arc that sweeps out the vertices of triangle 2 is clockwise, while the arc that sweeps out the vertices of triangle 3 is counterclockwise.

An algorithm for correcting winding order errors

The invariant preserved by this algorithm is that all triangles in tris have consistent winding order.

The algorithm initially places a single triangle into the buffer without considering its winding order. This is ok since winding order can only be consistent or inconsistent. If a mesh has one triangle then be definition it has consistent winding order.

Next it finds a triangle that has not been added to tris, but that is adjacent to one of the triangles currently in tris. That triangle is checked for winding order consistency with triangles in tris using the ordered edge rule. It is flipped if it needs to be flipped, and then added to tris. The process continues until all triangles are in tris.


template<typename Triangle>
std::vector<Triangle>
fix_wind_errors(const std::vector<Triangle>& triangles) {
  vector<Triangle> tris;
  vector<unsigned> remaining_inds = inds(triangles);

  unsigned num_added = 0;
    
  while (remaining_inds.size() > 0) {

    for (auto ind : remaining_inds) {
      Triangle next_t = triangles[ind];
      vector<Triangle> sub_tris =
        select(tris, [next_t](const Triangle t)
               { return share_edge(next_t, t); });

      if (sub_tris.size() > 0) {
        Triangle corrected = correct_orientation(next_t, sub_tris);
        tris.push_back(corrected);

        remove(ind, remaining_inds);
        num_added++;
        break;
      }

      if (num_added == 0) {
        tris.push_back(next_t);

        remove(ind, remaining_inds);
        num_added++;
        break;
      }
    }

  }


  return tris;
}

Helper functions


template<typename Triangle>
bool
share_edge(const Triangle tl,
       const Triangle tr) {
  int num_eq = 0;
  for (unsigned i = 0; i < 3; i++) {
    for (unsigned j = 0; j < 3; j++) {
      num_eq += (get_vertex(tl, i) == get_vertex(tr, j)) ? 1 : 0;
    }
  }
  return num_eq > 1;
}

  
template<typename Triangle>
bool winding_conflict(const Triangle ti, const Triangle tj) {
  for (unsigned l = 0; l < 3; l++) {
    unsigned lp1 = (l + 1) % 3;
    for (unsigned k = 0; k < 3; k++) {
      unsigned kp1 = (k + 1) % 3;

      if (get_vertex(ti, k) == get_vertex(tj, l) &&
        get_vertex(ti, kp1) == get_vertex(tj, lp1)) {
        return true;
      }

    }
  }
  return false;
}

template<typename Triangle>
Triangle flip_winding_order(const Triangle& t) {
  Triangle f;
  set_vertex(f, 0, get_vertex(t, 1));
  set_vertex(f, 1, get_vertex(t, 0));
  set_vertex(f, 2, get_vertex(t, 2));
    
  return f;
}

template<typename Triangle>
std::vector<Triangle>
flip_winding_orders(const std::vector<Triangle>& vertex_triangles) {
  vector<Triangle> tris;
  for (auto t : vertex_triangles) {
    tris.push_back(flip_winding_order(t));
  }
  return tris;
}

template<typename Triangle>
Triangle
correct_orientation(const Triangle to_correct,
            const std::vector<Triangle>& others) {
  auto ti = to_correct;
  for (auto tj : others) {
    if (winding_conflict(ti, tj)) {
      Triangle corrected = flip_winding_order(ti);

      return corrected;
    }

  }

  return ti;
}

Convenience functions

std::vector<T>
select(const std::vector<T>& v, F f) {
       std::vector<T> selected;
  for (auto e : v) {
    if (f(e)) {
      selected.push_back(e);
    }
  }
  return selected;
}


template<typename E, typename T>
void remove(E e, T& t) {
  t.erase(std::remove(begin(t), end(t), e), end(t));
}

C++ Data Structures: std vector vs. std list for Delete Only Workloads

I know, I know. A workload with only deletes isn't exactly realistic, but I thought it would be interesting to take a look at how std::vector and std::list compare in this extreme case.

Untitled

BENCHMARKING CODE: https://github.com/dillonhuff/list_deletes

Interestingly, vector does much better for all but the smallest of list sizes. My intuition (not a great guide for computer program performance) was that linked lists would do better for workloads with many random deletes, since modifying a linked list takes constant time, while modifying an array based list takes linear time.

What that intuitive guess misses is that before the constant time modification can take place the program has to traverse to the element being deleted. This traversal takes O(n) time and has much worse locality than the O(n) copy performed by an array based list, so for small objects like ints the performance of list is actually worse than the performance of vector.

Example: Build, Install and Use a Shared Library with CMake

FULL CODE LINK: https://github.com/dillonhuff/cmtest

Most examples of how to use CMake either show how to build a shared library and then use those shared libraries in the same project, or just show how to build executables for a project.

I had a hard time finding a clear example of how to build a shared library, install it (in my case in /usr/local/) and then use the installed library in a new project, so I decided to create one myself.

The code link above is a git repo with 3 directories:

  1. simple: a tiny example library with one function, that is built and installed using CMake
  2. user_project: a tiny "application" that links to simple along with the compile command I used on mac (OS X 10.11.3)
  3. cmake_user_project: another "application" that links to the simple_lib library. It is built with CMake instead of a simple compile command

A simple C++ parser for binary STL files

FULL CODE LINK: https://github.com/dillonhuff/stl_parser

STL format (*.stl) is a file format used to store shapes. It is common in computer aided design (CAD), and computer aided manufacturing (CAM), especially in 3D printing.

STL files describe a 3D shape as a triangulation of the surface of a part.

According to wikipedia, https://en.wikipedia.org/wiki/STL_%28file_format%29, an STL file has 3 parts:

An 80 byte header

A 4 byte sequence encoding the number, N, of triangles as an unsigned int

A list of N triangles. Each triangle is composed of:

  1. A normal vector (3 floats) so that identifying the inside and outside of the triangular mesh is easy
  2. 3 vertices, each of which is a vector of 3 floats
  3. A UINT 16 for attributes