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!