tracelog troubles fixed!

I had to do some tracelog stuff at work and it took me a couple of days to figure out how to enable tracelog for drivers at boot. Hopefully this will save time for the next guy who has to deal with this.



Scenario:
You're a conscientious developer who's sprinkled WPP_TRACING macros all over (and I mean, ALL OVER) your Windows driver. The driver goes out into the real world, and everything is fine, until one day you have a customer complaining that the driver is not working as it should. It's giving some cryptic (or worse, generic) error. You think, "Hmm... thank FSM that I used WPP. I'll just grab the tracing files from the offending computer & figure out what went wrong". That's where this blog post comes in handy.



Steps:

1. Substitute as needed. I've used these defaults to make the steps clear:

<arch> = x64.

<LoggerName> = MyDriverLogger. This is an arbitrary name that is used to register the autologger.

<ETL File> = MyDriverLog.etl. Arbitrary named WPP trace log file.

<Driver WPP GUID> = 144EBFEE-C4AD-4A88-B8AC-3B7F7E5AD442. This is from your WPP_DEFINE_CONTROL_GUID typically found in your trace.h file.

<Logger GUID> = C7A7ACEB-9A80-4898-98F0-E3F9A5F043FE. The logger name needs a unique GUID.



2. Send the customer three files. tracelog.exe (found in WinDDK\7600.16385.1\tools\tracing\<arch>\), a batch file called 'AddAutoLogger.bat'. This file contains a single line:



tracelog -addautologger MyDriverLogger -guid #144EBFEE-C4AD-4A88-B8AC-3B7F7E5AD442 -matchanykw 0x7FFFFFFF -sourceguid #144EBFEE-C4AD-4A88-B8AC-3B7F7E5AD442 -sessionguid #C7A7ACEB-9A80-4898-98F0-E3F9A5F043FE -flag 0xFFFF -level 0xFF -f %WINDIR%\Temp\MyDriverLog.etl -cir 2



Also send the customer a batch file called 'RemoveAutoLogger.bat' which contains:


tracelog -flush MyDriverLogger

tracelog -remove MyDriverLogger



2. Ask the customer to do the following:

a. Open an admin command prompt and cd to the location where the files are, and run 'AddAutoLogger.bat'.


Developer verification for step 2: If you are trying it on your system, you can open 'Regedit', Navigate to HKLM\System\CurrentControlSet\Control\WMI\AutoLogger. You should see a key called 'MyDriverLogger'. Verify:

1. Start = 1
   
2. GUID =C7A7ACEB-9A80-4898-98F0-E3F9A5F043FE
   
3. File=%WINDIR%\Temp\MyDriverLog.etl
   

There will be a single sub-key in MyDriverLogger. This is the GUID '144EBFEE-C4AD-4A88-B8AC-3B7F7E5AD442'. Verify:

1. Enabled=1
   
2. EnableLevel=0xFF
   
3. MatchAnyKeyword=0x7FFFFFFF
   

3. Ask the customer to perform the activity that causes the problem, or wait for a specified period of time.


4. Ask the customer to open command prompt again and cd to the directory and run RemoveAutoLogger.bat.


Developer verification for step 4: There should be a new file called %WINDIR%\Temp\MyDriverLog.etl.



5. Ask the customer to mail the file to you.


Developer verification for step 5: Check your email and see if the file is attached. :)



Now, the customer's job is done, and it's up to you to show off your debugging chops!

1. Grab the source corresponding to the driver.
   
2. Make a build (the configuration and architecture don't seem to matter).
   
3. Run 7600.16385.1\tools\tracing\\tracepdb.exe -f . You get a brand new .TMF file.
   
4. Run 7600.16385.1\tools\tracing\\traceview.exe. Select 'Open an Existing File'. Select the .etl file. In the next step, select the .TMF file and add the newly created .TMF file.
   
5. Enjoy the WPP trace!!
   

References:

1. ETW EtwRegister() provider list. [http://www.adras.com/ETW-EtwRegister-provider-list.t4828-192-1.html]. Thank you, thank you, Ivan
2. Tracelog command syntax. [http://msdn.microsoft.com/en-us/windows/hardware/ff553012]
3. Using TraceView. [http://msdn.microsoft.com/en-us/windows/hardware/ff556063%28v=VS.85%29]
4. TracePDB [http://msdn.microsoft.com/en-us/windows/hardware/ff553043%28v=VS.85%29]
   

Longest subsequence (contd.)

Unfortunately, the solution I've suggested fails if the sequence is say, 10, 13, 12, 1, 2, 3, 4, 5. The solution is 5, but the above algorithm returns 2.

This means that a single stack is unlikely to solve the problem. We need a list of stacks, each starting off with the first number that cannot be added to an existing stack. Here's what the code looks like:

List<Stack<int>> stacks = new List<Stack<int>>();

foreach (int incoming in sequence)
{
    bool makeNew = true;
    foreach (Stack stack in stacks)
    {
         if (stack.top() < incoming)
         {
             stack.push(incoming);
             makeNew = false;
         }
    }

    if (makeNew == true)
    {
        Stack<int> s = new Stack<int>();
        s.Push(incoming);
        stacks.Add(s);
    }
}

And at the end, the solution is the stack with the maximum Count.

This *almost* works. It fails to get the correct solution in a very interesting way. Consider the sequence, 10, 20, 30, 12, 13, 14, 15. The solution is 5 (10, 12, 13, 14, 15), but the algorithm will return the solution as 4 (12, 13, 14, 15).

Here's how it works. The algorithm creates a new stack for element 10. It then pushes 20, and 30 onto this stack. The next element 12 cannot be put into an existing stack, so it creates a new one and pushes to the new stack. The next elements 12, 13, 14, 15 are added to the top of the new stack giving a solution of 4.

So, we always need a stack handy with just the element 10 in it for the algorithm to succeed.

List<Stack<int>> stacks = new List<Stack<int>>();

foreach (int incoming in sequence)
{
    bool makeNew = true;
    foreach (Stack stack in stacks)
    {
         if (stack.top() < incoming)
         {
             Stack<int> dupStack = new Stack<int>();
             //Copy the elements of stack to dupStack.
             stacks.Add(dupStack);
             stack.Push(incoming);
             makeNew = false;
         }
    }

    if (makeNew == true)
    {
        Stack<int> s = new Stack<int>();
        s.Push(incoming);
        stacks.Add(s);
    }
}

This ensures that even when we add an element to an existing stack, the unchanged stack is also present in the list of stacks. This algorithm gives the correct solution under all circumstances.

Correctness accomplished!

Now, for optimization...

Here's an interesting observation: We are running the algorithm above, and we have a list of stacks. Consider 2 stacks in the list. They both have the same elements (Count is the same). However, the top element in stack B is larger than the top element in stack A. Given a new incoming element which is greater than both the top elements of A and B, either stack can work. In other words, since we need only one stack with that height, the stack with the smaller top value should be preferred. We can safely delete the stack with the larger top value. The end result will be unaffected.

So, after adding the element to the stacks, we can run though all stacks and compare them to each other. If the Count of 2 stacks is the same, delete the one with the larger top value.

List<Stack<int>> toDelete = new List<Stack<int>>();

foreach (Stack<int> a in stacks)
{
    foreach (Stack<int> b in stacks)
    {
        if (a == b)  //No need to compare the same objects.
            continue;

        if (a.Count == b.Count && a.Top() < b.Top())
            toDelete.Add(b);          
    }
}

foreach (Stack s in toDelete)
{
     stacks.Remove(s);
}

And finally, one more thing. The solution does not ask for the list in the largest sub-sequence. It asks simply for the count. Given that, we don't even need a family of stacks. We can simply do with a KeyValuePair where the first int remembers the height of the "stack" and the second contains the Top value of the stack.

The solution becomes space efficient. Instead of keeping a bunch of stacks in memory, it remembers a pair of numbers per stack. So, if the largest sub - is 100, the maximum number of elements that are stored in memory is 100 * 2 integers.

Since a pair of integers given that the key will always be unique can be stored in a single Dictionary, it prob. makes sense to make a single dictionary and work the algorithm around that.

I will write up that code on request.

Ding! Leveled up.

New skill added.

Git user: +5

Git administrator: +5

Longest subsequence

Surfing Hacker News the other day, I came across this fascinating article about Palantir's interview process. How to Rock an Algorithms Interview.

I thought I would write my thought processes to one of the Gild.com code challenges that I attempted some time back.

The problem statement is in essence, given a sequence of unsorted integers, find the count of the longest sequence of monotonically increasing numbers in the original sequence.

So, here's my thought process towards the solution:

Tip: I read it in a book somewhere, but the author says (paraphrased) "Fix the data structure, and the algorithm will become readily apparent". This has been a very useful guide in all my programming tasks.

The first thing that came to mind when I saw this problem was "stacks". The solution has to involve stacks in some way. There has to be some function within the algorithm that says, given a stack of numbers on it, check the next number in the sequence and add it to the stack only if the number is greater than the one already on stack.

Stack<int> s = new Stack<int>();

foreach (int i in list)
{
  if (i > s.top())
  {
      s.push(i);
  }
}

Given a sequence of say "1 20 10 11 12 21", the solution should be "5" (1 10 11 12 21), but the naive implementation would solve to "3" (1 20 21). I thought I would add a fix that would replace the top on the stack with the next number if the next number is less than the top.

Stack<int> s = new Stack<int>();

foreach (int new in list)
{
  int top = s.pop();

  if (new > top)
  {
     s.push(top);
     s.push(new);
  }

  if (new > s.top() && new <= top)
  {
      s.push(new); //Replace the top value with the smaller value
  } else
  {
      s.push(top); //Put back the original value...
  }
}

To be continued..

Welcome

Hi,

This is my new blog about programming and debugging.