What block allocation algorithm does NTFS use?

Question

On Windows XP 64, I downloaded a 1.2 GB file and it ended as fragmented as the image shows. Unfortunately, before taking the snapshot from Piriform Defraggler I defragmented the other files, so you can't see the exact state at the point the file was written. However, the disk was all the time about as empty as now (25% used) and hardly fragmented.

What block allocation algorithm does NTFS use? It looks like random or maybe putting it where the disk head actually stands.

UPDATE:

This is what happened today after writing 67 MiB of a new file. It got splitted in 731 fragments of average size of only 95 KiB. The file was used to fill some gaps, but not all of them, it doesn't use the huge continuous free space either. Strange, isn't it?

UPDATE 2:

Unlike PC Guru, I really don't think Opera is the culprit. I think it (as opposed to Google Chrome) doesn't tell Windows the expected size, however, there are many cases when it's not possible and it's the responsibility of the OS to handle it in a sane way. The following picture shows what happened after a couple of days with me doing nearly nothing on this partition - the TEMP directory and all my data (except for those managed by Windows) are both located elsewhere. Windows itself seems not to use SetEndOfFile and fragments its own files in a terrible way (600 fragments for a couple of small file of about 40 MB). NTFS doesn't seem to use the first available sector, as there are again files in the middle and also near the end of the quite empty disk (usage 23%), so the exact algorithm is still unknown.

Answer 1

IIRC, the NTFS filesystem attempts to allocate the file in contiguous storage. However it can only do that if the filesystem knows the size of the file. If you open a file and start writing to it, it'll write to the "best" place to fit the file (typically towards the outside of the platter). But that "best" place might not be big enough to fit the file.

If the application tells NTFS the actual size of the file (with SetEndOfFile()), NTFS can do a better job of finding contiguous space for the file (the SetEndOfFile API causes NTFS to allocate storage for the entire file).

Answer 2

Your problem must be with Opera. I have just looked at a bunch of files on a very full and fragmented drive. Large files downloaded using Chrome were all contiguous.

This suggests that Chrome knew the size of file at the start of download, so told NTFS the size of file to expect. If you do that NTFS will try to place file in a single fragment, or when no fragment is big enough, into the largest available fragments. Interestingly it always uses these fragments in descending order of size, so large files copied by Explorer onto a fragmented drive, can jump around all over the drive.

Where the program does not know the file size, or does not bother to tell NTFS, but instead just opens a file and starts writing sequential data, it appears that NTFS acts very similar to FAT32, which simply starts at the first available cluster (or the first one available after the last allocated in that session) then uses whatever is available from there forward. As an example, at about the same time I asked CCleaner to scan the registry, causing it to back it up to a large txt ".Reg" file. This file started near the start of drive and then was scattered across 127 different fragments. Unlike files copied with Explorer, or downloaded with Chrome, in every file I looked at, the clusters were allocated in ascending order.

For this research I used Winhex (free trial version available from Winhex.com). When looking at a directory entry. right-click on a filename and choose Position, List Clusters, to see list of clusters used by that file.