Powershell goodies

I posted a blog last time about my attempt to learn PowerShell again and I found that it is quite interesting to learn this new scripting language on Windows. Yes, there are many scripting languages available on other platforms but on Windows none of them really works great in my opinion not because they are bad but because they are not really meant for Windows. I guess we can argue about that all day but in any case I would like show another way to increase your PowerShell knowledge. That is PowerShell Code Repository! This web site has many many interesting scripts that can be used right away.

For instance, for years every time I wanted to list only directories in my current location, I had to search online to figure out how to do it or run 'dir | more' and look for myself. Then, as I began to learn PowerShell, I found that I can do this with 'dir | where-object { $_.psiscontainer -eq '$true' }' but that is too long to type.
Then I found a script that will reduce my keyboard typing effort. That is 'Compare-Property' function from PowerShell Code Repository. With this function, I can do the same task in the following manner.


PS >Set-Alias ?? Compare-Property
PS >dir | ?? PsIsContainer

Pretty cool. So all you have to do is to go the site and see if you have any scripts that you want to use. Then download them and keep them in one specific folder. After that, include that folder in your $profile as follows.

$env:path = $env:path + ";c:\scripts"

Once you do that, you can just use script name 'Compare-Property' like the above example as if it is regular PowerShell regular cmdlets. So that's all for now and happy PowerShell!

Powershell works differently

For years I tried to pick up powershell but everytime I tried, I miserably failed to feel comfortable about it. But I felt strongly that I need to learn some scripting language to automate some works on Windows so I decided to give it a try one more time.

This blog is by no means to say that I have mastered it but I think that I finally understood why I could not learn the powershell. I think that is because I approached powershell from my bash scripting experience. What do I mean by it? When we use bash shell, we work with string but when we work with powershell, that does not work well. Powershell always returns objects not string and hence when we want to process output of certain output, it is necessary that we approach it from this perspective. So let me illustrate this.

Often times we want to list something and then 'grep' certain words from the list output. For instance, let us try 'alias' command on powershell.

Alias command produces lots of output that its output is more than a page. So probably I want to see if alias output has the line that contains the word 'content' in some easy way. Readily I think of 'grep' command and I remember that select-string works somewhat similarly. So let us try Select-String.

Hmm. Nothing... But I know that there is a line that has the word 'content' What's going on here? Apparently, Select-String is only looking for words to match from Name column. So let us now try 'asnp' to verify it.

Ok, that is better but I want to get the entire line. What should I do?
This is where I realized that powershell works on objects not string. In principle, powershell operates on objects and hence when the powershell returns the output for alias command, it actually returned the list of objects. So if we want to get the whole line which in this case is an object, we want to try to match the entire object. Here is the trick.

Yes, we got what we wanted. Again, this is because we were looking for object where its definition contains 'content' and it returns the list of those object.

In summary, powershell operates on objects so when you use powershell, keep that in mind!

Increase the productivity with raid0

Yesterday I was busy setting up my machine at work and one of my co-workers shared the tip to increase the machine throughput so let me share here with all of you.
Every time we build the projects or do some IO intensive works, things get slower because of the bottleneck with the disks. Hence if we can avoid writing to/reading from the disk, the productivity increases and there are numerous examples out there with this idea and probably one of well-known example is memcache.

So what can we do about disk IO? If we have to write to the disk in any way, there is a way to improve the situation with raid0. Normally whenever we think about the raid, we tend to think about redundancy but raid0 is not so much about that. What raid0 is doing is striping. According to wiki page, it is defined as follows.
A RAID 0 (also known as a stripe set or striped volume) splits data evenly across two or more disks (striped) with no parityinformation for redundancy.


In my machine, I happen to have two additional disks and hence my co-worker suggested me to use raid 0 to boost the IO and that is what I did. So how did I do it? It turned out that it is fairly easy to do it on Windows. Here is the steps.
First let us fire up 'Computer Management' by first going to 'Control Panel' and selecting 'Administrative Tools' and finally choosing 'Computer Management' icon. Once you have it running, click 'Disk Management' under 'Storage'. When you do that, you will see all your disks and its partitions and there choose two disks that you want to use for raid0 and right click mouse and you will see the menu as follows.

Choose 'New Striped Volume...' and when you do that, you will be presented a couple of windows to configure the raid0 such as allocating the size of the disk for raid0.
Once you do that, you are done. Yes, I know it is too simple. But that's all it takes. Now when you look at the 'Disk Management' console, you will see something like the following.

I created the raid0 and label it as E: drive and hence I put my source code there so that all the IO work happens there to isolate the IO from other OS or app activities. So if you are a windows user and have some extra disks on your machine, give it a try!

Signed or Unsigned?

I found it confusing at times to understand signedness of integer and hence I have attempted to tackle some of these issues here. First, the task I want to discuss here is the internal representation of a given number in a signed and unsigned integer type and I think that this will help me to have a better understanding of signedness.
To illustrate the point, let us assume that we need to develop a function that should return the absolute value of input number. For this task, can we just return the same value but specify that the return type of unsigned as follows?

Unfortunately, this will not work properly. For example, if we pass a negative value to the above function and assign the returned value to the unsigned type of integer, we will see that the function somehow did the trick. However, if we assign the returned value to the signed type of integer, it will still display the negative value. Why is that? That is because we have not actually changed anything. Let me explain with an example. Say, we pass '-1' to unsigned_abs() function, this passed value is represented as 32 1's in a binary format. This value is interpreted as '-1' in a signed integer but that same value is interpreted as 0xffffffff in a unsigned integer.

So then what should we do? Here is one way to implement abs() function.

This will actually update the internal value of input value and return the real absolute value. To verify this, I wrote a function to display the binary value of an input integer as follows.

The above function simply uses STL stack to store binary values of the input value and prints out on the screen and when I executed the returned values from unsigned_abs() and signed_abs(), I could see that the returned value of unsigned_abs() is displayed as 32 1's but the returned value of signed_abs() is displayed as '1' when I called binaryrep().

In conclusion, we need to be careful of what's really taking place when we use either unsigned and signed and in my opinion, if we are not sure, I would recommend to just use signed integer.

Take advantage of chromium project!

This post is going to be very short. In this post I just wanted to share my experience with chromium browser project. Not that I have ever contributed to chromium project but as I read/study the code for my own edification, I found it very useful.


I found that there are many parts of code that I can use for my various needs and as we know the code quality must be good.
For instance, I recently found that how to dump stack trace on Windows. Earlier last year I tried to do the similar thing on Linux but I never knew that the similar API exists on Windows. But thanks to these projects, I found the working example code of stacktrace code. The list can go on and on and what's neat about this project is that it has the code that is doing the same thing on Linux, Windows, and Mac so if you need to write code for all these platforms in C/C++, check it out! Lastly, I hope that I will be able to contribute to the project in the near future.

Breadth First Search and Backtracking

This week I had a chance to look at Topcoder.com tutorial and read about BFS/Backtracking. Sometimes it is not clear if we need to use BFS or Recursion/backtracking approach to solve a given problem and the following is the BFS description from Topcoder.com

Breadth First Search (BFS):
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. Besides this, certain ways of passing from one point to another are offered, all of them having the same cost of 1 (sometimes it may be equal to another number). Often there is given a N x M table (formed of N lines and M columns) where certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one. Such tables may represent mazes, maps, cities, and other similar things. These may be considered as classical BFS problems. Because BFS complexity is in most cases linear (sometimes quadratic, or N logN), constraints of N (or M) could be high - even up to 1 million.

Having said that let me post two problems that sound somewhat similar but require different approach to solve. First question. We have a robot sitting somewhere in the matrix and we want to find the shortest path to get to a certain position. This is a kind of problem that needs BFS approach as described above. Whenever we see the shortest and the cost to move from one state to another is same, it is safe to assume that we can use BFS. As we know from graph theory, we use BFS to find the shortest path and hence we can apply BFS to solve the problem and the key to remember is that BFS requires us to use queue-like data structure. At each node, we need to enqueue the neighboring nodes for the future processing and we do this this until the queue is empty. When the queue is empty, we know that we have covered all the nodes that could be reached from the source node. Lastly, for this particular problem we want to keep the number of paths taken so far and use that to calculate the next one by simply adding one.

Second question. How do we find the possible number of paths from one node to another for a robot to take? In this problem, we do not concern the shortest path but would like to know how many paths exist from the source node to the destination node. This is somewhat simple problem in that we just need to recursively call ourselves until we get to the destination. For this particular problem, we need backtracking because we want to keep track of states between each call and thus, we will need to use backtracking technique.
Here is the better description of backtracking from Topcoder.com:

Backtracking:
This technique may be used in many types of problems. Just take a look at the limits (N, M and other main parameters). They serve as the main hint of a backtrack problem. If these are very small and you haven't found a solution that's easier to implement - then just don't waste your time on searching it and implement a straight-forward backtracking solution. 

Usually problems of this kind ask you to find (similarly to Brute Force):

1. Every possible configuration (subset) of items. These configurations should respect some given rules.
2. The "best" configuration (subset) that respects some given rules.

What does that mean? It means that we do not want to explore the path that we have already visited. In other words, we keep the states so far and add the next route and try the next route that's available. Why? In the next move, we normally want to know where we have visited to make a decision. However, when we come back from the next move, we want to take out the next move we just added and add another route that we have not tried yet.

Again, it is possible that the question may ask to calculate the shortest path but the cost for each move differs. For Backtracking problem, it normally asks for finding all the possible paths or some sorts so let us keep that in mind to differentiate.

So in conclusion, look for some keywords when we need to solve problems.
If it states the shortest path with the same cost for each move, try BFS. But if it asks us to find all possible paths or each cost differs, try to see if we can use Backtracking.

p.s. Let me add two samples: one for bfs and the other for backtracking for future reference.

• bfs sample: https://github.com/yeilho/algorithms/blob/master/shortest.cc
• backtracking sample: https://github.com/yeilho/algorithms/blob/master/bridge.cc

WinHttpSendRequest is not so easy to use

The other day I tried to look up WinHttpSendRequest() API for more information and found that the second entry in google search result was my question that I posted at MSDN forum two years ago with regard to its usage example.
At that time I was trying to understand how to use WinHttpSendRequest() API to construct Http POST request and could not find any good example on the web and hence, I decided that I should write something about it in my blog.

Followings are the basic flow of WinHttp calls to create Http Post request.

• Prepare WinHttp session handle and connection handle. We can reuse these two handles to send multiple requests. For this use WinHttpOpen and WinHttpConnect API
• Create a specific WinHttp request handle. Once we have the request handle, we can associate certain options with this handle. Use WinHttpOpenRequest.
• Construct POST request and details are as follows. This is where it gets real tricky.

In order to successfully send our Http Request, we need two APIs: WinHttpAddRequestHeaders() and WinHttpSendRequest()

First, I assume that we want to send multipart form HTTP Post request to upload a file along with some fields. For this task, we need to specify our intention but what's tricky is the fact that we need to specify the boundary of http header so that Web server knows where the header ends and how to parse our request. Here is an example of its usage.

WinHttpAddRequestHeaders(
    hRequest, 
    "Content-Type:multipart/form-data; boundary=----------ThIs_Is_tHe_bouNdaRY_$", 
    -1L, 
    WINHTTP_ADDREQ_FLAG_ADD
);

As you can see, we have put certain string such as "boundary=----------ThIs_Is_tHe_bouNdaRY_$" to inform the web server to look for these string to parse the request correctly.

Now, it is time to construct all the fields. Let me give you one example of form field.
Say we have a field called "username" and want to specify its value "ilho". Following is the sequence of string we need to construct and just to make it easy to read, I added 'new line' after '\r\n' but in reality you need to have all the strings together as one string. You need to add the same format for all the fields to the same string.

------------ThIs_Is_tHe_bouNdaRY_$\r\n
Content-Disposition: form-data; name="username"\r\n\r\n
ilho\r\n

For data file that we want to upload, we need special care. Now, assume that we want to upload some text file. Here is the string that you want to build.

------------ThIs_Is_tHe_bouNdaRY_$\r\n
Content-Disposition: form-data; name="personal_data";\r\n filename="personal.txt"\r\n
Content-Type: text/plain; charset=utf-8\r\n\r\n

Finally, you will need to end your request by specifying the ending as follows.

\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n

I know that these look really ugly and I do not know if there is any better way to do this. Unless I am mistaken, I think for this specific part, I prefer to use curl because it is a lot easier to use curl to construct POST request than WinHttp.

But for now, let me throw out some code example to illustrate what we need.

StringCbPrintf(
    ffield,
    sizeof(ffield),
    "------------ThIs_Is_tHe_bouNdaRY_$\r\n"
    "Content-Disposition: form-data; name="username"\r\n\r\n"
    "ilho\r\n"
);

StringCbPrintf(
    filefield,
    sizeof(filefield),
    "------------ThIs_Is_tHe_bouNdaRY_$\r\n"
    "Content-Disposition: form-data; name=\"personal_data\"; filename=\"personal.txt\"\r\n"
    "Content-Type: text/xml; charset=utf-8\r\n\r\n"
);

StringCbPrintf(formdata, sizeof(formdata), "%s%s", ffield, filefield);

Once we have the form ready, we need to calculate the entire size of request which includes the actual text file. With all these information, here is WinHttpSendRequest.

total_length = strlen(formdata) + filesize + strlen("\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n");


WinHttpSendRequest(
    hRequest,
    WINHTTP_NO_ADDITIONAL_HEADERS,
    0,
    (LPVOID)formdata,
    (DWORD)strlen(formdata),
    total_length,
    0
);

Once we send our HTTP request, we can start to send our text file using WinHttpWriteData followed by boundary string to finish the HTTP Post request. Hence, in minimum we need to call two WinHttpWriteData.

WinHttpWriteData(file content);
WinHttpWriteData("\r\n------------ThIs_Is_tHe_bouNdaRY_$--\r\n\r\n");  // boudary

At this point, we just need to receive the Web server response to your request by calling WinHttpReceiveResponse() API and we are pretty much done by now.

In the above example, I tried to present the steps in a rather raw format but in reality you may want to create either inline functions or macros to to reduce the typings and create a nice interface to work with WinHttp. Like I said, if you need to work on the similar code for both Windows and Linux, it is better off to use curl and I hope that MS will come up with better APIs or interfaces for the developers to work with Http requests.

Windows Startup Routine

It's has been a while since I looked at Windows startup routine and I realized that I don't remember the overview of it. So I grabbed Windows Internals and summarized it here for my future reference.

1. POST (Power On Self Test)

2. BIOS loads MBR into memory

3. MBR reads the first sector from the bootable partition and the code in the first sector loads the Bootmgr into memory

4. Bootmgr loads the boot loader, Winload.exe (Ntldr in the past)
Winload.exe
- loads the appropriate kernel and HAL images (Ntoskrnl.exe and Hal.dll)
- reads registry to determine boot device drivers and loads them.
- calls KiSystemStartup in Ntoskrnl.exe

Ntokrnl.exe
- phase 0
 prepares data structures for services to run in phase 1
 calls the object manager, security reference monitor, process
manager, user-mode debugging framework, and the Plug and Play manager initialization
- phase 1
 calls more initializations i.e. power manager, memory manager
 I/O manager initialization
 - creates I/O manager object types i.e. device, driver
 - perform boot-start drivers initialization and system-start device drivers are loaded and initialized
 - the Session manager(Smss) process is started. Smss is responsible for creating user-mode environment that provides the visible interface to Windows

Smss
 - start the Windows subsystem
 - start Csrss which is Client Server Runtime Process
  - CSRSS: user-mode portion of the Win32 subsystem; Win32.sys is the kernel-mode portion.
 - launches Windows Initialization Process (Wininit) and start the interactive   logon manager process (Winlogon)

Wininit
 - performs startup steps such as creating the initial window station and desktop objects
 - creates SCM which initializes auto-start services and drivers

Once Winlogon validates the logon, Winlogon sets up the user environment and starts the shell(explorer)


That's it for now and hopefully, in the future I will try to add some diagram to describe what I wrote in the above.

global/static variables - where are they?

At church today I met a person who is also a programmer and he seems to be well versed in C++. As we talked, he asked me a question about C++ related questions but as for me, I just started to work on my C++ as I have been using C for the past few years. Hence, I could not answer to his question clearly. His question was that when we declare static variables inside the class, where they go in the process memory.

In the past, I worked on ELF and PE on Linux/Windows but that did not really help me much to answer his question so when I came home, I decided to first write a C code and verify the location of static/global variables. In theory, global variables that are not defined should go to 'data' section and those that are either defined to be zero should go to 'bss' section. But for those that are defined to be non-zero, I am not sure. So let me find out where they are.

So first let me show my C code.

int g_init_var1 = 3;
int g_init_var2 = 0;
int g_un_var;

int testfunc(int num)
{
   int auto_var;
   static int static_var_1 = 0;
   static int static_var_2;

   if (num == 1)
       static_var_2 = num;
   return 0;
}

int main(int argc, char *argv[])
{
   int num;

   scanf("%d", &num);
   testfunc(num);

   return 0;
}

I just declared two global variables and two static variables and after that I compiled the code with /FA option to produce assembly code.

C:\> cl /FApe.asm pe.c

When I looked at assembly code, I found the following.

PUBLIC  _g_init_var1
PUBLIC  _g_init_var2
_DATA   SEGMENT
COMM    _g_un_var:DWORD
_DATA   ENDS
_BSS    SEGMENT
_g_init_var2 DD 01H DUP (?)
?static_var_1@?1??testfunc@@9@9 DD 01H DUP (?)      ; `testfunc'::`2'::static_var_1
_BSS    ENDS
_DATA   SEGMENT
_g_init_var1 DD 03H
$SG2474 DB  '%d', 00H
ORG $+1
$SG2475 DB  '%d', 0aH, 00H
_DATA   ENDS
_BSS    SEGMENT
?static_var_2@?1??testfunc@@9@9 DD 01H DUP (?)      ; `testfunc'::`2'::static_var_2
; Function compile flags: /Odtp
_BSS    ENDS

As expected cl put g_un_var into 'data' segment because it is not defined. But I found it interesting to see what happens to the global variables that are defined. The global variables that are defined to be zero are actually located in 'bss' segment while the global variables that are defined to be non-zero are located in 'data' segment.
For static variables, we see the same pattern. The only thing I would comment is that g_init_var1/g_init_var2 is the type of PUBLIC but g_un_var is the type of COMM. Linker will concatenate all PUBLIC segments having the same name to form a single, contiguous segment. But with COMM, it creates a communal variable which behaves like external variables and communal variables are allocated by the linker. In a nutshell, they are just like global variables but we cannot assign them initial values and the only drawback of using communal variable is that they may not appear in consecutive memory locations.

After this exercise, I try the same on linux to see if there is any difference and the following is the result of objdump.

Disassembly of section .data:


00000000006008b8 <__data_start>:
6008b8:   00 00                   add    %al,(%rax)
...


00000000006008bc <g_init_var1>:
6008bc:   03 00                   add    (%rax),%eax
...


00000000006008c0 <static_var_1.2130>:
6008c0:   01 00                   add    %eax,(%rax)
...


Disassembly of section .bss:


00000000006008c8 <dtor_idx.6147>:
...


00000000006008d0 <completed.6145>:
6008d0:   00 00                   add    %al,(%rax
...


00000000006008d4 <g_init_var2>:
6008d4:   00 00                   add    %al,(%rax)
...


00000000006008d8 <static_var_2.2131>:
6008d8:   00 00                   add    %al,(%rax)
...


00000000006008dc <g_un_var>:
6008dc:   00 00                   add    %al,(%rax)
...

On Linux I found the similar principle applied. The global variable that is defined to be non-zero is located in 'data' segment but the global variable that is either undefined or defined to be zero is located in 'bss' segment. This is interesting part. If you remember, we saw uninitialized global variable was put in 'data' segment on Windows but on Linux they are located in 'bss' as Linux initialize them to be zero. The same applies to static variables on Linux. I also added the explanation on COMM directive in the above so please refer to it and the link below for more information.

So today's exercise helps me to visualize where the global/static variables go and let me finish my post with a couple of links that I referred to verify my theory.

- MASM Documentation

- Paradigm Assembler User's guide : for communal variables

- x86 Disassembly/Variables

- Peering Inside the PE

Useful links for Windows kernel development

This post may not be real interesting post but for those who are interested in working on Windows kernel module especially Windows Filtering Platform, let me list all the URLs that I referred while working on kernel module.

• Windows Driver Kit Documentation
• Driver Development Intro
• DDKWizard Homepage - for VS integration
• Sources FILE - MSDN
• Getting started with the Windows Driver Development Environment
• Kernel-mode code signing walkthrough
• From Sample Code to Production Driver: What to change in the sample - MSDN
• ALE Layers - MSDN
• WFP Forum - recognize when TCP connection terminated
• Question on MmMapViewInSystemSpace at Osronline
• Tooling around with Vista
• Remote Debugging with VMWare
• How to return the number of elements required for subsequent calls?
• Kernel mode code-signing walkthrough
• Multiple filter conditions not working on Vista
• Poolmon usage

Palindrome implementation using recursion

My co-worker mentioned a problem of checking palindrome of the word that is made up with linked list. So basically each character is connected via linked list and the task is to find out if the given linked list contains a palindrome word.

This is pretty simple if we want to implement in a iterative way using some data structure such as stack. However, I find it worth trying to implement the code using recursion.

So the idea is that I need to pass two arguments and I need to somehow to keep one pointer pointing to one end and the other pointer to the other end. This way, as we traverse we move each pointer two different directions and compare the value. If the value does not match, the word is not a palindrome word.

With that then, let me show my function.

int palindrome(node **head, node *cur)
{
  int ret = 1;
  if (cur) {
      ret = palindrome(head, cur->next);
      if (cur->data != (*head)->data) {
          cout << cur->data << "-" << (*head)->data << ": not a palindrome" << endl;
          ret = 0;
      }
      *head = (*head)->next;
  }
  return ret;
}

I think that recursion is one of those techniques that every programmer should be comfortable with and if I find more problems on recursion, I will work on it and post it here again.

Calling fopen_s/_wfopen_s with ccs=UNICODE flag

Just recently I had a discussion with my co-workers about my program that has to interact with Web servers via HTTP post. In my program I post a file and I told my co-worker that the file is in the format of UNICODE.

However, when he tries to decode it, he found that the file is actually not in the format of UNICODE especially not in UTF-16 but in the format of ANSI. So I said to him that it is not possible because I create a file by explicitly specifying that the file should be in the format of UNICODE. But close examination of my file showed that the file is indeed in ANSI format. So I quickly looked at my code where I create a file.

Here is the code.

_wfopen_s(&fp, filename, L"w+, ccs=UNICODE");

Then, I looked up MSDN and found the following.

Allowed values of the encoding include UNICODE, UTF-8, and UTF-16LE. If the file is already in existence and is opened for reading or appending, the Byte Order Mark (BOM) is used to determine the correct encoding. It is not necessary to specify the encoding with a flag. In fact, the flag will be ignored if it conflicts with the type of the file as indicated by the BOM. The flag is only used when no BOM is present or if the file is a new file. The following table summarizes the modes used in for various flags given to fopen and Byte Order Marks used in the file.

Encodings Used Based on Flag and BOM

Flag	No BOM (or new file)	BOM: UTF-8	BOM: UTF-16
UNICODE	ANSI	UTF-8	UTF-16LE
UTF-8	UTF-8	UTF-8	UTF-16LE
UTF-16LE	UTF-16LE	UTF-8	UTF-16LE

As you can see above, if it is a new file and I specify UNICODE, it is actually creating a file in the format of ANSI. Obviously I missed that and I somehow thought that the file would be created in the format I specified.

So the lesson I learned from this incidence is that I should be more careful reading MSDN page. Lastly, here is MSDN link to fopen_s/wfopen_s: http://msdn.microsoft.com/en-us/library/z5hh6ee9(v=vs.80).aspx

Priority Queue

Lately I have been studying Jon Bentley's book "Programming Pearl" and in the book it talks about priority queue with heap data structure. So I grabbed another book "Algorithms in C by Robert Sedgewick" and read more about it as it sounds pretty useful for many different applications.

According to these two books, a priority queue is a data structure to insert data and retrieve the item with either largest key or smallest key depending on your heap setup. We can implement priority queue using many different data structures but heap seems to be very good candidate. I borrowed two fundamental heap functions: siftdown() and siftup(). siftdown() sifts the first element down the data structure until it has either no child or it is larger than its children node and siftup() does the opposite.

So decided to implement it based on these two books and even though I referred the books, it was still somewhat tricky to get it right.

Tricky part was that I have to take care of a node with one child during siftdown(). At first I tried compare the node with both child in my while() loop but that did not work well. So referred the Algorithms in C for help and learned this edge case.

Followings are the code based on the two books I mentioned above. It needs more work if I need to use it for real but this should at least help me to get going.

typedef int node;
static node *pq;
static int N;

#define swap(a, b) \
  do { node tmp = *a; *a = *b; *b = tmp; } while (0)

class prioQ
{
private:
  node *pq;
  int count;
  int max_num;

public:
  prioQ(int imax)
  {
      max_num = imax;
      pq = new node[max_num+1];
      count = 0;
  }
  ~prioQ()
  {
      delete pq;
  }
  int empty()
  {
      return (count == 0);
  }
  int insert(node v)
  {
      if (count >= max_num) {
          std::cout << "Queue is full." << std::endl;
          return -1;
      }
      pq[++count] = v;
      siftup(pq, count);
      return 0;
  }
  node delmax()
  {
      if (empty()) {
          std::cout << "No more item in the queue." << std::endl;
          return -1;
      }
      swap(&pq[1], &pq[count]);
      siftdown(pq, 1, count-1);
      return pq[count--];
  }

  // helper functions from max heap
  void siftup(node a[], int k)
  {
      while ((k > 1) && (a[k] > a[k/2])) {
          swap(&a[k/2], &a[k]);
          k = k / 2;
      }
  }
  void siftdown(node a[], int k, int end)
  {
      int i;
      while (k*2 <= end) {
          i = k * 2;
          // k*2 < N is to test one child node case
          if ((k*2 < end) && (a[i] < a[i+1])) i++;
          if (a[k] > a[i]) break;
          swap(&a[k], &a[i]);
          k = i;
      }
  }
};

By the way I used http://www.simplebits.com/cgi-bin/simplecode.pl?mode=process to copy my C++ code. It works great!

sleep() does not put the process to sleep

Just recently I had to deal with the code that calls sleep() and suddenly I wondered if sleep will put the entire process to sleep. So I quickly checked man page and found the following.

SYNOPSIS
#include

   unsigned int sleep(unsigned int seconds);

DESCRIPTION
sleep() makes the current process sleep until seconds seconds
have elapsed or a signal arrives which is not ignored.

At first, I believed this man page but it just happened that I read Jefferey Rithcer's Windows Via C/C++ a few days ago and I remembered that on Windows there is no SuspendProcess() even though there is SuspendThread(). Jefferey explained that it is not quite possible to have SuspendProcess() in that Process can have many threads and these threads can come and go. Hence, it is pretty difficult to get all the threads to be suspended on Windows as thread is a scheduling unit.

Though I am looking at Linux for this particular case, it seems to me that I should check this out with other developers so I posted the question on stackoverflow(http://stackoverflow.com/questions/6192645/does-calling-sleep-from-pthread-put-thread-to-sleep-or-process).

Sure enough, I got an answer that my man page is outdated and I need to report to maintainer of man page to update the man page of my distribution. So the correct description of sleep is as follows. (taken from http://www.kernel.org/doc/man-pages/online/pages/man3/sleep.3.html)

SYNOPSIS
#include

   unsigned int sleep(unsigned int seconds);

DESCRIPTION
sleep() makes the calling thread sleep until seconds seconds have elapsed or a signal arrives which is not ignored.

So in conclusion, sleep() puts the calling thread to sleep not the process. Interesting!

C# with ntdll call? Not so easy

Lately I started to study C# and this was due to the fact that I had to use it for my work. I have been using C most of the time so it is somewhat difficult for me to switch the language but I think that this is a great chance to learn the new language as it helps me to think differently when approaching the problems.

Anyhow, today I decided to try my C# to do things that are somewhat low-level and I know that C# is not designed for low-level tasks but wanted to try how it is like with C#. So I decided to get to Process Environment Block(PEB) and find the command-line arguments of a given process. In this particular example, I just used my own process but it is relatively easy to change it to point to other process by providing other process handle.

With that, let me show my code.

using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.Diagnostics;
using System.Runtime.InteropServices;

namespace PEB
{
class Program
{
  enum PROCESSINFOCLASS : int
  {
      ProcessBasicInformation = 0,
      ProcessQuotaLimits,
      ProcessIoCounters,
      ProcessVmCounters   // omitted the rest
  };

  [StructLayout(LayoutKind.Sequential)]
  public struct PROCESS_BASIC_INFORMATION
  {
      public int ExitStatus;
      public int PebBaseAddress;
      public int AffinityMask;
      public int BasePriority;
      public int UniqueProcessId;
      public int InheritedFromUniqueProcessId;
      public uint Size
      {
          get { return (6 * sizeof(int)); }
      }
  };
  // following two definitions are from Windows via C C++
  // check 'allow unsafe code' in properties page
  [StructLayout(LayoutKind.Sequential)]
  unsafe struct __PEB
  {
      public fixed uint Filler[4];
      public uint InfoBlockAddress;
  };
  [StructLayout(LayoutKind.Sequential)]
  unsafe struct __INFOBLOCK
  {
      public fixed uint Filler[17];
      // Windows keeps this as Unicdoe(wide character)
      // Without the following option, it only gets to the first character
      [MarshalAs(UnmanagedType.LPWStr)]
      public string cmdAddress;
  }

  // Finding NtQueryInformationProcess API from ntdll is relatively easy
  [DllImport("ntdll.dll", SetLastError = true)]
  static extern int NtQueryInformationProcess(
      IntPtr processHandle,
      PROCESSINFOCLASS processInformationClass,
      ref PROCESS_BASIC_INFORMATION processInformation,
      uint processInformationLength,
      ref int returnLength);

  static void Main(string[] args)
  {
      int status;
      int returnLength = 0;
      Process currentProcess = Process.GetCurrentProcess();
      PROCESS_BASIC_INFORMATION pbi = new PROCESS_BASIC_INFORMATION();

      status = NtQueryInformationProcess(
          currentProcess.Handle,
          PROCESSINFOCLASS.ProcessBasicInformation,
          ref pbi,
          pbi.Size,
          ref returnLength);

      if (status == 0)
      {
          Console.WriteLine("PEB address: {0}", pbi.PebBaseAddress);
          // It is little tricky to do casting in C# - two steps
          // First, it is necessary to get the pointer
          // Second, cast that to what we need using Marshal.PtrToStructure
          IntPtr pebAddress = (IntPtr)pbi.PebBaseAddress;

          __PEB peb = (__PEB)Marshal.PtrToStructure(pebAddress, typeof(__PEB));
          IntPtr infoblkAddr= (IntPtr)peb.InfoBlockAddress;
          __INFOBLOCK infoBlock =
                 (__INFOBLOCK)Marshal.PtrToStructure(infoblkAddr, typeof(__INFOBLOCK));
          Console.WriteLine("command line: " + infoBlock.cmdAddress);
    
      }
  }
}
}

I put comments on my code to explain what I am trying to do but basically at the end of the day, the lesson I learned from my exercise is that I should choose the right language for the job. I felt that C# is probably not the best language to work on low-level ntdll stuff. I think that for this kind of job C/C++ is better language. Perhaps it is just that I am still in the process so I am just not good.

Anyway, I am enjoying learning C# so hopefully next time, I will write something more meaningful and related to C#.