Antimail

In the past, I presented various ways to browse these mysterious device objects called "shadow copies". Shadow copies are static images in time (snapshots) of your volume contents, at some point in the past. These shadow copies are volumes on their own, with a file system namespace accessible through the regular Win32 APIs such as FindFirstFile/FindNextFile. For example the existing sample code in MSDN for these APIs that enumerates files on a real volume will work just fine on a shadow copy volume. In fact, that's how all backup applications are accessing shadow copy content today.

So, if these devices are real volumes, how can we view them in Explorer? It turns out that you can't view them by default - this is simply because these are volumes without an associated drive letter or root mount point. However, in XP or Windows Server (and Vista), you can still access these shadow copies by assigning them a drive letter using utilities like DOSDEV, or by doing tricks with the FOR command, etc. 

Now, if you have Vista, it is much simpler to access shadow copy devices directly from Explorer. The trick is to use a new feature called Symbolic Links: to access the contents of a shadow copy as a "directory", simply create a symbolic link to the device. Vista also includes a convenient command-line tool called MKLINK.EXE to create symbolic links, which makes this operation very easy.

Here is an example of accessing the contents of a shadow copy device. The first step is to enumerate shadow copies on the machine, using the VSSADMIN LIST SHADOW command. This will give us the devices and also a creation timestamp.

C:\Windows\system32>vssadmin list shadows |more
vssadmin 1.1 - Volume Shadow Copy Service administrative command-line tool
(C) Copyright 2001-2005 Microsoft Corp.

Contents of shadow copy set ID: {c72c8036-d563-43c8-b351-1994dfad580a}
   Contained 1 shadow copies at creation time: 2/23/2008 9:59:04 AM
      Shadow Copy ID: {f3727808-bea6-4b59-bef7-6849ee721709}
         Original Volume: (C:)\\?\Volume{3e83355f-7c0e-11dc-b416-806e6f6e6963}\
         Shadow Copy Volume: \\?\GLOBALROOT\Device\HarddiskVolumeShadowCopy4
         Originating Machine: Adi-Game-PC
         Service Machine: Adi-Game-PC
         Provider: 'Microsoft Software Shadow Copy provider 1.0'
         Type: ClientAccessibleWriters
         Attributes: Persistent, Client-accessible, No auto release, Differential, Auto recovered

Contents of shadow copy set ID: {0bf23f77-8461-4869-b391-da4d213940a5}
   Contained 1 shadow copies at creation time: 2/24/2008 4:00:24 AM
      Shadow Copy ID: {87d59b22-9e84-4d0d-81ca-2b565d6f7e55}
         Original Volume: (C:)\\?\Volume{3e83355f-7c0e-11dc-b416-806e6f6e6963}\
         Shadow Copy Volume: \\?\GLOBALROOT\Device\HarddiskVolumeShadowCopy5
         Originating Machine: Adi-Game-PC
         Service Machine: Adi-Game-PC
         Provider: 'Microsoft Software Shadow Copy provider 1.0'
         Type: ClientAccessibleWriters
         Attributes: Persistent, Client-accessible, No auto release, Differential, Auto recovered

C:\Windows\system32>mklink /d c:\shadowcopy \\?\GLOBALROOT\Device\HarddiskVolumeShadowCopy5\
symbolic link created for c:\shadowcopy <<===>> \\?\GLOBALROOT\Device\HarddiskVolumeShadowCopy5\

C:\Windows\system32>dir c:\shadowcopy
Volume in drive C has no label.
Volume Serial Number is 4A02-860C

Directory of c:\shadowcopy

12/14/2007  01:46 AM    <DIR>          Asi
01/15/2008  12:56 AM    <DIR>          bin
12/13/2007  11:59 PM    <DIR>          debuggers
12/13/2007  11:55 PM        17,644,031 dir.log
01/14/2008  11:41 PM    <DIR>          Downloads
01/01/2008  05:50 PM    <DIR>          dumps
12/30/2007  11:43 PM    <DIR>          garbage
01/08/2008  11:13 PM    <DIR>          Garmin
10/15/2007  09:03 PM    <DIR>          Intel
12/30/2007  11:59 PM    <DIR>          Program Files
01/27/2008  01:32 AM    <DIR>          Program Files (x86)
01/15/2008  12:17 AM    <DIR>          test
01/30/2008  06:52 AM    <DIR>          Users
12/14/2007  01:55 AM    <DIR>          WinDDK
02/13/2008  05:23 AM    <DIR>          Windows
02/21/2008  10:43 PM    <DIR>          Work
               1 File(s)     17,644,031 bytes
              15 Dir(s)  147,657,666,560 bytes free

That's it. Now I have a persistent link called c:\shadowcopy which points to the contents of the shadow copy device - which is the image of my C:\ drive at 4:00 AM (this is when my latest system restore point was created).

A new notes,though:

1) Make sure you use the "/D" option in MKLINK so you create a directory-based, not a file-based symbolic link

2) Make sure you append a backslash to the shadow copy device in the MKLINK command (marked in red above)

If this made you interested about shadow copies - note that you can create, enumerate and delete shadow copies programatically using either VB scripts that use the WMI API for shadow copy administration, or by using the VSS API (documented publicly on MSDN). Sample code is available in the Platform SDK as well.

I love this - if you have kids, and if you are a geek, you'll understand.

http://gizmodo.com/photogallery/microserveces08/1000446145

The title sums it all.

P.S. And, as a Christmas bonus, here is a nice chess puzzle.

In the above diagram you must add the two missing kings in such a way that White, who is on the move, can deliver immediate mate, i.e. mate in one move.

[source: ChessBase]

A review in ComputerWorld features the new Samsung's 64 GB Flash drive:

Samsung rates the drive with a read speed of 100MB/sec and write speed of 80 MB/sec, compared to 59MB/sec and 60MB/sec (respectively) for a traditional 2.5" hard drive. We ran several benchmarks. In our HD Tune performance tests, the drive turned in an average transfer speed of 28.6 MB/sec with .3ms average access time. Burst speed was 25.5MB/sec with 4.5% CPU utilization. HD Tach tests using both 8MB and 32MB blocks for testing measured the burst speed at 30.8MB/sec, the average sequential read speed at 28.0MB/sec. HD Tach won't measure write speeds on primary drives, so we turned to Fresh Diagnose, which reported an average write speed of 11.65 MB/sec.

With such a spectacular performance, it's easy to see why Flash drives will become the next top-of-the-line feature in any high-end laptop, maybe more important than a high-speed CPU.

I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came across recently. Many people that got confronted with it said bluntly that the problem simply has no solution, otherwise it would contradict common sense, information theory, etc. But surprisingly, it does have a solution.

For X% strictly bigger than 50% the solution is known as the MJRTY algorithm, discovered a while back by R.S. Boyer and J.S. Moore (also called the Majority Vote algorithm). Although the algorithm is deceptively simple, its proof is not. the In the PDF cited above, the authors present a complete proof and also some interesting history around this non-trivial result.

The correct algorithm was also found by Lailin Chen - also presented in the post comments, but without a proof:

Well, Since we already knew there is one and only one who has more votes than any others, we can find him by letting the votes "fight" each other:

Picked the first one, say X1, count 1 for X1, then move on,  if X1 repeats, add count to X1.

When X1 doesn't repeat, reduce the count by one, if it reaches 0, picked up the current one (say X2), and do the some counting to X2. 

Keep doing this until the end. The last one left with a counting bigger than 0 is the leader:

X3  X1  X1  X2  X1  X3  X3  X3  X4

   ^

X3, 1

X3  X1  X1  X2  X1  X3  X3  X3  X4

         ^

       X3, 0

X3  X1  X1  X2  X1  X3  X3  X3  X4

               ^

            X1, 1

X3  X1  X1  X2  X1  X3  X3  X3  X4

                     ^

                   X1, 0

X3  X1  X1  X2  X1  X3  X3  X3  X4

                           ^

                          X1, 1

X3  X1  X1  X2  X1  X3  X3  X3  X4

                                 ^

                               X1, 0

X3  X1  X1  X2  X1  X3  X3  X3  X4

                                       ^

                                    X3, 1

X3  X1  X1  X2  X1  X3  X3  X3  X4

                                             ^

                                           X3, 2

X3  X1  X1  X2  X1  X3  X3  X3  X4

                                                    ^

                                                  X3, 1

So X3 is the winner.

Here is a more formal description of the algorithm:

- You have with two registers: an “candidate register” containing the name of some candidate (candidate), and a counter (counter).

- Candidate_register = NULL;

- Counter = 0

- For each new candidate:

     If (Candidate_register is NULL)

            Candidate_register = candidate

            Counter = 1

     Else If (candidate == candidate_register)

            Counter++;

     Else if (counter > 0)

            Counter --;

            If (counter == 0)

                Candidate_register == NULL

- At the end you have the correct candidate in the register.

For X < 50% we can adapt a more complex variation of the same algorithm which requires two passes instead of a single one. Instead of keeping a single register (keeping the last candidate) and its associated counter, we keep a number of K registers (with their associated counters) and run the same algorithm. The integer K is chosen such that 100/(K+1) < X. After this pass, we discovered K candidates but of course the candidate with the biggest counter might not be the real candidate. To find the top candidate we simply reset all counters to zero (but keep the candidates found) and re-run the same algorithm.

- Instead of maintaining one “element” register and one counter as in the main algorithm, you need to use K registers, each with K counters.

- First pass

     Initialize all candidate registers with NULL and counters with zero

     For each candidate in the log file

          If the candidate is in one of the K registers, increase its counter

          Else if there is one candidate register which is NULL, put it there and increase its counter with 1

          Else, reduce all counters by 1

               If some counters become zero, set their corresponding candidate registers to NULL

     At the end, each of the candidate registers contains every element with frequency > 100/(K+1). One of them is the winner

- Second pass

     Initialize all counters with zero, but keep the candidate registers filled with the values above.

     For each candidate in the log file

          If the candidate is in one of the K registers, increase its counter

     At the end, you have all the correct counters for all the candidate registers.

     Select the one that has the maximum count.

A variation of this second algorithm is briefly mentioned in this presentation although I could not find a formal article describing it.

What all these algorithms have in common? The fact that you know ahead of time that there is a winner, but you don't know which one. While the algorithms are simple to implement, this is a pretty strong condition that is not likely to be encountered in our real world. Maybe on a planet called Xen :-)

A few completed transactions:

- $420: http://cgi.ebay.com/Microsoft-ZUNE-2-Gen-Black-80-GB-mp3-NEW-NIB-EXTRAS_W0QQitemZ320182867203QQihZ011QQcategoryZ147175QQssPageNameZWDVWQQrdZ1QQcmdZViewItem 

- $405: http://cgi.ebay.com/Microsoft-ZUNE-2-Gen-Black-80-GB-mp3-NEW-NIB-EXTRAS_W0QQitemZ320183303981QQihZ011QQcategoryZ147175QQssPageNameZWDVWQQrdZ1QQcmdZViewItem

- $399: http://cgi.ebay.com/Microsoft-Zune-2-Gen-Black-80-GB-20000-Songs-Dig_W0QQitemZ320182491104QQihZ011QQcategoryZ147175QQssPageNameZWDVWQQrdZ1QQcmdZViewItem

I just started to play with HD Tune, just to get a tool to look at my S.M.A.R.T. data. Not that I trust SMART a lot, but I wanted to see what's there.

So that's how I discovered my main drive has a bunch of reallocated sectors. Ouch!

What is a reallocated sector? Whenever a sector becomes "bad" for some reason, modern harddisks are "remapping" this sector to some other location of the disk. That's why you almost never see "bad clusters" on a modern harddisk. See for example the result of the CHKDSK command on the same drive - it says that everything is fine:

C:\Windows\system32>chkdsk c:
The type of the file system is NTFS.

WARNING!  F parameter not specified.
Running CHKDSK in read-only mode.

CHKDSK is verifying files (stage 1 of 3)...
  118464 file records processed.
File verification completed.
  129 large file records processed.
  0 bad file records processed.
  2 EA records processed.
  75 reparse records processed.
CHKDSK is verifying indexes (stage 2 of 3)...
  460369 index entries processed.
Index verification completed.
  5 unindexed files processed.
CHKDSK is verifying security descriptors (stage 3 of 3)...
  118464 security descriptors processed.
Security descriptor verification completed.
  16840 data files processed.
CHKDSK is verifying Usn Journal...
  35955328 USN bytes processed.
Usn Journal verification completed.
Windows has checked the file system and found no problems.

244196351 KB total disk space.
104969600 KB in 101394 files.
     50680 KB in 16841 indexes.
         0 KB in bad sectors.
    227651 KB in use by the system.
     65536 KB occupied by the log file.
138948420 KB available on disk.

      4096 bytes in each allocation unit.
  61049087 total allocation units on disk.
  34737105 allocation units available on disk.

There are two problems with reallocated sectors. First, each harddisk comes with a limited "pool" of empty sectors that can be used as reallocated sectors. When you run out of those, then the automatic protection goes away, so you will start seeing more and more bad sectors at the OS level.

Second (and most importantly) there is a performance problem with reallocated sectors. Due to the fact that some sectors are remapped to another area on the disk, sequential I/O on those sectors is getting randomized (becomes random I/O) with very different performance characteristics. How big is the performance impact? Pretty big. Let's say that you have a no reallocated sectors in a 40 MB interval. If you want to read 1 MB in this interval, you will read it at a standard sequential I/O rate, say about 50 MB/s on a regular SATA disk. So reading will take 1/50 = 20 ms.

Now, let's pretend we have a reallocated sector in the middle of the 1 MB that we want to read. The reading time will include those 20 ms above plus the two additional seeks. Since a seek is usually around 8-9 ms (or even more) for a standard SATA harddisk, you get around 40 ms for reading the 1 MB which is twice as long. So, from a bandwidth perspective, you are reading that 1 MB at 25 MB per second, which half of the actual speed. So what might see is a sudden decrease in sequential I/O bandwidth whenever there is a reallocated sector around.

The interesting thing is that you can "spot" the approximate location of reallocated sectors by doing a sequence of sequential reads over the entire harddisk (from the beggining to end) and see where you have sudden drops in I/O performance. Fortunately, the same tool mentioned above - HD Tune - has a benchmark mode which allows precisely this.

Here is the picture of my backup drive (a Hitachi 250 GB drive):

You can see that the transfer rate decreases smoothly from 60 MB/s (near to the outer region of the disk) to 30 MB/s (near to the center of the disk). There are no sudden drops. In contrast, here is a disk with a lot of reallocated sectors:

You can see a lot of drops along the blue sequential read path, with a variability of about 50% in some cases.

Note - if you are doing these sequential I/O tests, make sure that your harddisk is not in use by any other applications or the page file - this will cause additional seeks which would "pollute" the original graph.

For that reason, I haven't run yet the benchmark on my main drive since I know that paging will distort the results - I'll try this later ...

A fascinating article in ACM Queue examines the various ways in which a harddisk can fail.

Here is an example - the fault tree for reading failures.

There is a huge amount of aliens living on the Xen planet who want to elect their new leader (since their previous leader died a while back). They want to switch to a very democratic voting process, through the help of a very special communication field called the “vortessence”.

One interesting property of voting through vortessence is that it can tell them whether there is a certain unique leader which is guaranteed to meet a certain percentage of votes X% (which is a number chosen ahead of time and can be considered constant in this discussion). But the vortessence cannot be used to tell who is actually the winning leader.

So these aliens will also use the help of a computer to record the voting. The rules are simple:

1. The winner has to record at least X% votes (a unique leader is guaranteed to exist, as indicated by the vortessence)
2. Each alien votes exactly once, by indicating the name of the proposed leader.

After the voting season, the votes are recorded in a very large unsorted log file, containing the names of the voted aliens. Now, since there are a lot of aliens, they need to use an algorithm to figure out the leader, running in O(1) in space and O(N) in time (name comparisons can be considered constant).

In what conditions is this problem solvable, and if yes, what is the minimal number of log passes?

There is a new article in the hard-to-discover http://support.microsoft.com world, about various improvements of defrag in Vista. In summary: defragmentation is now performed automatically by default (at 1 AM on every Wednesday - that is, if your laptop is not powered off) and it works nicely in an incremental manner - no need to restart a full new defrag every time.

Here is an excerpt:

Partial defragmentation

By default, the defrag tool only defragments files smaller than 64 megabytes (MB). Therefore, files larger than 64 MB are not moved unnecessarily. You can use the -w parameter to tell the defrag tool to defragment all files, regardless of size.

Cancellable defragmentation

In earlier versions of Windows operating systems, if the defrag engine was in the middle of a large move request, it could take lots of time to cancel defragmentation. In Windows Vista, the defrag engine processes input and output requests in smaller portions. Therefore, you can avoid situations where the defrag engine is busy with processing large move requests when you cancel a defragmentation session.

Low priority defragmentation

The defrag engine in Windows Vista does not affect the performance of other processes that are running on the computer. Other processes are not affected because defragmentation runs as a low priority process. And, defragmentation uses only minimal CPU resources and memory resources. If the system is using lots of CPU resources and memory resources, the defragmentation process may take a longer time to finish.

Ability to defragment volumes with less free space

You can defragment volumes in Windows Vista when volumes have less free space than is the case in earlier versions of Windows operating systems.

Faster defragmentation

In some defragmentation modes in Windows Vista, defragmentation of a volume is two or three times faster than defragmentation in earlier versions of Windows. Windows Vista uses significantly improved algorithms that move files toward the front of the hard disk. In earlier versions of the defrag engine, the defrag engine defragmented data at the end of the hard disk before the defrag engine defragmented the data toward the beginning of the hard disk.

Scheduled defragmentation

You can now use Task Scheduler to schedule defragmentation. Therefore, you do not have to manually start defragmentation. By default, a task is created and is set to run at 1 A.M. on every Wednesday. If the computer is turned off or if the task does not run at the scheduled time, the task will run the next time that the computer is idle.

Shadow-copy-aware defragmentation

In shadow-copy-aware defragmentation, defragmentation uses Volume Shadow Copy Service (VSS) in-box software to optimize defragmentation. The VSS software minimizes copy-on-write change blocks. Shadow-copy-aware optimization slows down filling the difference area. This kind of optimization also slows down the reclaiming of old snapshots during defragmentation.

Master File Table (MFT) defragmentation

If the MFT is spread into multiple fragments, the defrag engine can combine the MFT fragments during defragmentation.

Here is an interesting piece of spam I received this morning on our internal discussion list:

Dear VSS Lab Account,

    You were recently appointed as a biographical candidate to represent your industry in the Madison Who's Who Among Executives and Professionals, and for inclusion into the upcoming 2007-2008 "Honors Edition" of the registry.

     We are pleased to inform you that on October 4th, your candidacy was approved. Your confirmation for inclusion will be effective within five business days, pending our receipt of the enclosed application.

     The Office of the Managing Director appoints individuals based on a candidate's current position, and usually with information obtained from researched executive and professional listings. The director thinks you may make an interesting biographical subject, as individual achievement is what Madison Who's Who is all about. Upon final confirmation you will be listed among thousands of accomplished individuals in the Madison Who's Who Registry. There is no cost to be included.

     We do require additional information to complete the selection process and kindly ask that you access this form on our website:

Click here to register

Or you can manually enter this address into your web browser:

http://www.madisonwhoswho.net/basiclisting

To ensure your biographical data is received in time, please complete the online form above as soon as possible. Our editorial deadline is quickly approaching.

 

Sincerely,

Matthew Johnson
Managing Editor  

 

Madison Who's Who is not associated or affiliated with Marquis Who's Who or any other Who's Who.

Madison Who's Who, Inc. 30-01 Northern Blvd. Long Island City , NY 11101 USA

Great - so this would be our first occasion to promote our internal, super-secret VSS-related discussion list in a public Who's Who entry.

After I checked that the links are indeed not pointing to some sort of phishing-attack server, I went there and filled the forms - maybe we'll get approved!

I'll keep you in touch with the progress...

I sure hope that you will appreciate this - the .NET 3.5 source code will be publicly released. Initially, we will see .NET BCL, ASP.NET, Windows Forms, ADO.NET, XML and WPF. Later, more libraries will be added (WCF - yes!), LINQ and Workflow.

Just when we thought that there is no room more room on those little bits on a harddisk, Toshiba doubles their density again: http://www.newswire.ca/en/releases/archive/September2007/06/c5819.html 

From their press release:

Toshiba Corporation today announced a prototype hard disk drive (HDD) that uses Discrete Track Recording (DTR) technology to boost capacity to a record-breaking 120 gigabytes (GB) on a single 1.8-inch platter. The drive is the first in the world to apply DTR, a breakthrough technology that boost the areal density of a perpendicular magnetic recording (PMR) by a full 50 percent. Toshiba plans to start mass production of HDDs integrating DTR technology in 2009.

Florin Lazar, Todi Pruteanu si cu mine am demarat in cursul acestei saptamani un seminar tehnic pe teme de storage in Vista si programare distribuita in WCF. Mai multe detalii aici: http://reg.studentclub.ro.

Pana acum seminariile din Bucuresti si Cluj au avut un raspuns fantastic! Daca aveti opinii, impresii (pozitive sau negative) m-as bucura sa le puneti in sectiunea de comentarii...

Si nu in ultimul rand, multumiri lui Todi si Microsoft Romania pentru organizarea acestui eveniment.

A friend of mine didn't know about Windows Home Server - so I sent him these links:

-          Main site: http://stopdigitalamnesia.com

-          Interview with Charlie Kindel http://channel9.msdn.com/ShowPost.aspx?PostID=270965

-          Download: https://connect.microsoft.com/site/sitehome.aspx?wa=wsignin1.0&siteid=38

-          Articol on Wikipedia: http://en.wikipedia.org/wiki/Windows_Home_Server

-          Blog: http://blogs.technet.com/homeserver  

-          Press release: http://www.microsoft.com/Presspass/press/2007/jan07/01-08WindowsHomeServerPR.mspx