19 July 2017

APFS and fast catalog search

This is about FSCatalogSearch / searchfs support in macOS with the APFS file system.

Updated 3 Oct 2017: Find Any File 1.9 will support fast search on APFS on High Sierra (10.13) by using the searchfs function. Version 1.9 is currently in open beta, see the FAF web site.

Updated 25 July 2017: Clarified why FSCatalogSearch doesn't work on APFS, adds issue about hard links and 64 bit CNID resolving.

Some background on FSCatalogSearch in general


Programs like EasyFind and my own Find Any File (FAF) are able to search for file names (as well as file dates, sizes and a few other rarely needed attributes) on disks in a quite fast manner by using a little-known function macOS offers.

This Carbon level function is known as CatSearch or (FS)CatalogSearch and has been around for more than 25 years. There's also a BSD level function called searchfs.

The advantage of this function is that it performs the search for names at the file system driver level, meaning that when you search for files containing ".png" in their name, the file system can look at the entire directory tree much faster, sorting out the matches, and only report those to the program that initiazes the search and then shows the results to the user.

Without this special function, the search program would have to start at the root of the disk, read each folder (directory) recursively, and then sort out the matches itself, which all takes much more computing time.

For example, a search on a disk with millions of files and folders on it would take only a few seconds with FSCatalogSearch, whereas a classic recursive search would take minutes.

Getting even more technical


Apple added the FSCatalogSearch function in Mac OS long ago, after introducing the HFS file system. This was supported by the fact that  HFS did, unlike Window's FAT, arrange the entire directory tree in one large file on the disk, with interlinked nodes that did not match the hierarchical folder structure. FSCatalogSearch would then iterate over the nodes in a most efficient way, not caring about the folder structure, thereby minimizing disk seek times, which was a significant factor in disk access before SSDs. This also meant that FSCatalogSearch would only work on volume formats that used a single (invisible) file for its entire directory tree, meaning that FSCatalogSearch was never available for FAT disks, for instance. It would also be optimal for NTFS volumes, but since Apple never used NTFS other than to support reading from Bootcamp partitions, they never made the effort to add FSCatalogSearch to their NTFS file system driver.

What about APFS?


Now Apple is about to replace HFS(+) with APFS on macOS. And fans of EasyFind and FAF start wondering: Will I still be able to perform fast disk-wide file name searches the way I'm used to?

The good news is: The APFS file system code has support for the lower level searchfs function, and that's been already added in 2016, apparently, for OS X 10.12. Which ultimately means: Yes, FAF and EasyFind can continue to provide fast search on APFS formatted disks, provided extra work is put into updating the apps accordingly.

However, there are still some issues:
  • The high-level FSCatalogSearch does not work on APFS. Both EasyFind and FAF rely on this function and therefore won't find files the fast way on APFS volumes right now. The reason for this is that APFS uses larger values (64 bit) than HFS+ for identifying the files, and the FSCatalogSearch function cannot handle those larger values. (rdar://33454922)
  • As of now (10.12.6, 10.13 beta 3), the searchfs function does search case-sensitive and not case-insensitive as it should. That means that searching for ".png" won't find files using ".PNG". I confirmed this with an Apple engineer - it's a known issue, just one with a low priority right now. So, there's a chance that this will get resolved eventually, and I hope it'll be done before 10.13 is released. This issue may not get fixed for 10.12.x, though. We'll have to see what Apple does in this regard. (rdar://33455597)
  • Hard links can't be identified correctly - if there are multiple hard links to the same file, then searchfs can't currently tell them apart, and the results will all point to the same directory entry. (rdar://33473247)
  • searchfs() returns CNIDs (Catalog Node IDs, 64 bit wide) instead of paths to the found items. This requires resolving these IDs to the paths later. However, there is currently no documented API provided in macOS to do so. There's a hackish way around this, but that's not a proper solution. (rdar://33507188)

What this all means


Current versions of FAF and EasyFind can't fast search on APFS. They need to be rewritten using the searchfs API.

I will be working on a quick-fix version of FAF that'll add fast search on APFS and which I hope to release before 10.13 (High Sierra) is officially released. I have quite a few other improvements for FAF in the works (64 bit app, content search, icon view, server support etc.) which will have to wait so that I can get this APFS issue resolved ASAP.

05 July 2017

Recover lost BootCamp Windows partitions on a Mac

I have installed several Windows 7 and 10 version on several of my Macs using Apple's Boot Camp feature.

Recently, I found that almost all of them have disappeared: I was not able to boot from them any more when I held down the option (alt, ⌥) key at startup - the Windows partitions would either not appear at all or not boot up.

The main reason in my case was that the MBR was reset to a plain GUID entry, and my Windows versions do not like that, because they cannot handle the EFI / GUID partition info that the Mac prefers. Why that even happened? Probably from repartitioning operations I frequently perform on my disks - and Apple's Disk Utility is quite ignorant of the needs to keep Windows bootable in this regard.

To fix that, the MBR partition info needed to get fixed, in order to make the Windows NTFS visible again to the Windows boot system.

The easy way


After writing this article initially, I learned that there is a Mac program, WinClone,  that can fix this issue with a few clicks, in case you do not want to mess with it yourself as shown below.

The hard way


I used iBored to edit the partition layout of each disk that contains a BootCamp partition from something like this:


Into this:


Note that this reduces the size of the first partition (you could as well change its size to the minimum, which is 33), and adds a new partition with the start and size matching what you can inquire using the Partitions window (see Disk menu):

This modification makes the Windows partition available in the MBR, and after that, I can boot again from it. And it won't mess with macOS booting because that uses the GUID partition info which isn't getting modified by this procedure (for more info, read my older article on using BootCamp on a non-startup disk).


08 April 2017

Adding fast external disks to various Mac models, with benchmarks

2nd Update on 9 Apr 17: See end of article
3rd Update on 18 Apr 17: Added more adapters

I wanted a fast external disk for my three Macs, which are now all 5 years or more old:
  • MacBook Pro Mid 2012 ("MacBookPro10,1"), 2.6 GHz Core i7
  • iMac 27" Mid 2011 ("iMac12,1"), 3.4 GHz Core i7
  • Mac Pro Late 2008 ("MacPro3,1"), 8 Core-Xeon 2.8 GHz

The Mac Pro has no Thunderbolt ports but I've installed a USB 3.0 PCI card from Inateck.

The iMac has Thunderbolt but only USB 2 built-in. I've added USB 3.0 support with the Elgato Thunderbolt 2 Dock (230 €).

I was interested to find out whether I should just go with a cheap USB 3 disk enclosure or use a significantly more expensive Thunderbolt enclosure.

The short answer is: If you have USB 3 ports on your Mac(s), you'll be fine with a USB 3 enclosure from a performance standpoint. But you won't get TRIM support, which is especially important if you plan to use the SSD as a faster boot volume - in that case, I recommend Thunderbolt instead.

For testing, I was using a new SanDisk Ultra II SSD 960GB (SATA III). I connected it to these adapters / enclosures:


Note: Even though the ICY BOX supports USB 3.1, which allows up to 10 Gbit/s, it connects to my Macs only at USB 3.0 speeds (5 Gbit/s) as they do not support 3.1. The provided USB cables are compatible with these Macs' "standard" USB ports.

The Thunderbolt enclosure by Delock requires an external power supply, and the AKiTiO comes with a second cable that needs to be plugged into a regular USB port to provide power to the disk. The USB adapters, on the other hand, do not have nor provide an extra power supply - they pull all the needed power for the disk from the USB port they're connected to.

Test Procedures


The testing was done in various ways, but I always only attempted to figure out the maximum possible transfer speed, such as for copying large single and unfragmented files, as that's the main use case for me (I often transfer entire disks, sector by sector, to another disk, e.g. for migration to a newer Mac, data analysis or quick backups).

For testing read performance, the easiest way is to use the dd command in Terminal.app:

sudo dd if=/dev/rdiskN of=/dev/null bs=512000

N has to be replaced by the disk number, which can be learned by using this command:

diskutil list

Note that this command lists the disk names with the leading "r", but when doing the test, the "r" is important for best speed results.

Write performance testing is a bit more difficult, because you need some data to copy from. You could use a file or another disk, but then you get a result that also involves the reading speed from the other disk. If that disk is an internal SSD, this may not affect the overall result too much, but in my case, it would, at least on the Mac Pro, despite having installed a Samsung SSD 850 EVO 1TB on a Velocity Solo x1 PCI card with a SATA III socket.

Copying with dd from /dev/zero may be a valid method for hard disks, but is not entirely honest for SSDs, as that would indeed test the transfer speed over the USB or TB bus, but since SSDs treat empty sectors specially, by not writing them to their flash memory, that would be cheating. I wanted to measure the true effective write speed, and therefore I'd need to write random (non-zero) data.

Copying from /dev/randon is no solution either, because generating the random data is very slow. I ended up getting unrealistic write speeds around 10 MB/s.

Being the author of a versatile disk editor, iBored, I have instead added a feature to it: Random data is generated once in memory, and then written repeatedly to disk, to consecutive sectors. That gives me realistic results that also correlated fairly well to copying from /dev/zero (i.e. it's a bit slower as expected). The version I used has not been officially released yet, but it's the 1.2b5 in the downloads. The Read/Write Speed Test commands are found in the Disk menu. If you try them yourself, be aware that this tool is not fool-proof. If you accidentally choose the wrong disk, and you could erase your precious files! So, be careful and always have an external backup, just in case.

Due to caching done by the SSD, I also had to make sure to write a large amount of data, to avoid reading and writing just through the faster cache.

Performance Test Results



The graphic does not include the Enateck, Teorder and AKiTiO adapters, as I got them later. The Teorder performed similarly to the Delock 42486, and the AKiTiO similarly to the Delock 42510. The Inateck is about 15 MB/s faster than the ICY BOX on the MacBook (didn't test on the other Macs, yet).

I also made a test on a PC with USB 3 ports, using iBored again. There, read speed was 240 MB/s with the Delock 42486 and the other USB3-SATA II adapter, and 320 MB/s with the ICY BOX. Write speed was only getting to 150 MB/s, though. That's odd, but a test with a regular Windows benchmark tool showed similar results.

Observations


  • The USB 3 performance with the Thunderbolt Dock is not as good as with the built-in USB 3 port on the MacBook Pro. That's not a weakness of the Dock, though, as far as I can tell, but a weakness of the iMac. I suspect its memory bus isn't up to it. When I connected the Dock to the MacBook Pro and then connected the ICY BOX to the Dock's USB 3 port instead of the MacBook Pro's port, I read at 330 MB/s and wrote at 300 MB/s, which is much closer to the built-in USB port.
  • The Delock 42486 USB 3 and the Teorder adapters are mislabelled in my opinion. Both supposedly support SATA III (i.e. 6Gbit/s) but perform like a SATA II (3Gbit/s) adapter.
  • My  Delock 42486 has a problem reporting incorrect power needs over USB, often just 24mA, when it needs 10 times or more, and that causes intermittend problems with some Macs but not with others. Delock support has not been helpful resolving this, insisting that it's not their fault, not even offering a replacement. This problem did not affect the performance testing, though.
  • The Thunderbolt adapters perform about as well or better as a good USB 3 adapter.
  • All the USB adapters have trouble reporting disk information such as name and serial number. While most at least report most of the disk's name ("Ultra II 960GB"), the ICY BOX only reports "ICY BOX" for any disk attached to it, the Inateck even just "2115". Only the Thunderbolt adapters are able to report the complete name ("Sandisk Ultra II 960GB") and the SDD's Serial Number to the Mac. These limitations with the USB adapters are minor, though, and will not affect performance or usability.
  • The Macs are also unable to report S.M.A.R.T. status for disks attached via USB - that's a known limitation of OS X / macOS. Again, with Thunderbolt there is no such issue.
  • UASP support may or may not be having a positive effect on performance. Obviously, the Teorder adapter, claiming UASP support, does not perform well at all. OTOH, the Inateck adapter is slightly faster than the ICY BOX, which may be due to UASP.

Conclusions


If you have a Mac that supports USB 3, there's hardly a need for the Delock Thunderbolt adapter.

The disadvantages of the Thunderbolt adapter (much higher price and having to use an extra power supply) have no advantages I can see.

The only exception I can think of is when you use disk in with that requires more power than USB 3 can supply. Though, my MacBook Pro, in System Profiler, under USB, tells me it can supply 1800mA, while the ICY BOX adapter with the SSD installed only requests 224mA.

It remains to be seen if faster disks (i.e. SSDs) are able to provide even more throughput, and if that would give the Thunderbolt adapter an advantage. However, I believe that SATA III, which is used by all three adapters as the interface to the disk, is the bottleneck here, though there is still a bit of room to fill that out (nominally, SATA III can transmit about 500 MB/s, and suppedly the SanDisk SSD can achieve that, but I have currently no way to verify this).

(9 Apr 17) After considering TRIM support, I've changed my mind on this: The lack of TRIM support in the tested USB 3 makes them not well suited for external SSDs as a Thunderbolt adapter that invariably supports TRIM. See below for more details.

If you have a Mac without USB 3 but with Thunderbolt, you still have two choices:

  • Either purchase a AKiTiO Thunderbolt adapter at about 125 € (as of 12 April 2017 at Amazon). That's probably the cheapest option in the short run.
  • Or get the Thunderbolt 2 Dock from Elgato at about twice the price, plus a cheap USB 3 enclosure for your disk. The Dock has the advantage that it equippes your Mac not only with three USB 3 ports but also with an HDMI port to connect a second monitor, an easier-to-access Audio port (which apparently is also higher-quality than that of some Macs) and even a microphone port. It is more bulky and requires a power supply, too (and here it makes actual sense). That leaves you with a slightly worse performance than with the Thunderbolt case, but therefore your external disk can be used even in older Macs that have no Thunderbolt, and even in regular PCs.

1. Update on 9 Apr 17:

@felix_schwarz pointed out to me that there's an advanced protocol for external disks called UAS (aka UASP). UAS can provide better performance USB (and, according to AKiTiO, apparently also over Thunderbolt), and Mac OS X supports UAS since 10.8, according to WP.

Of the adapters I tried, some claim UASP support, others do not. The results are inconclusive, as one adapter with UASP (Teorder) was very slow, whereas the one with it (Inateck) was slightly faster than the one without claiming UASP support (ICY BOX).

I just learned that AKiTiO makes various Thunderbolt products of interest. There is a Thunderbolt Dock with USB 3 ports as well as an External Thunderbolt + USB SSD that supports UASP. AKiTiO claims that this gives over 500 MB/s effective read speed with their 1TB SSD model, though their benchmark makes me wonder why the effective write speed is below 200 MB/s. Maybe they're using an older type of SSD that is not up to it. The Neutrino model seems to be better in this regard, but it does not offer a 1 TB SDD version. Also, the price is quite high compared to the setups I described above, although actual prices seem to be significantly lower that the given MSRP. If you need maximum performance, these SSDs may still be worth considering. (Update 18 Apr 17: I've now received and tested the AKiTiO Thunder SATA Go Adapter, see above).

2. Update on 9 Apr 17:

I had so far overlooked one important property that affects SSDs: Trim support.

It turns out that the tested USB 3 adapters provide no TRIM support. It's unclear why that is - I suspect that it's simply lack of support for it in OS X, similar to the missing S.M.A.R.T. support.

Missing TRIM support can will quickly lead to performance degradation of the installed SSDs.

If you only use hard disks with these adapters, that won't matter, but for SSDs, especially if they're used frequently for adding and deleting files, TRIM support is fairly significant to the performance. However, if the SSD is mainly used as a permanent backup device, e.g. as a Time Machine backup destination, TRIM support is not that important, even if files get replaced by TM once the disk is full.

Only the Thunderbolt adapters support TRIM. I've verified this by first checking in System Profiler whether the disk is even listed as "TRIM Support: Yes", and then by using the technique described in this Ars Technica article.

This realization inverts my earlier recommendation: Of the tested adapters, the ones with Thunderbolt are the best choice if you want lasting optimal performance, especially if you plan to boot from it regularly (which is a scenario for iMacs with only a HD installed, to speed up their system with the permanently connected SSD that'll host the system software). Of course, that still requires that you enable system-wide TRIM support in OS X / macOS, e.g. by using the "trimforce" command as explained in the Ars Technica article.



There is even an awkward work-around for missing TRIM support, in case you decide to go with an SSD and USB 3 regardless: Regularly fill the free space on the disk with a file that just contains zeros, and then delete the file again, as that'll tell the SSD that this space is actually unused, and should make the disk perform better again for a while. This can be done using iBored (menu Tools, Erase Unused Disk Space...) or with this Terminal command:

cp /dev/zero "/Volumes/YourSSDsName"

Once the copy has finished, filling up the entire disk, delete the file again:


rm "/Volumes/YourSSDsName/zero"


(Update 18 Apr 17): BTW, I now learned how to issue the TRIM command (only for supporting adapters, i.e. Thunderbolt) and will soon add this feature to my disk tool iBored.

28 March 2017

Xojo: How to improve performance when using WeakRefs

If you're building tree structures with leaves (children) that shall keep a reference to their branch (ancestor, parent) they're attached to, the simplest (but not smart) solution is to store a direct references to the parent object in the child object.

Imagine this node class:

class Person
  property name as String
  property parent as Person
  property children() as Person
end class

And then you'd have a Constructor like this:

sub Constructor (parentIn as Person, nameIn as String)
  self.parent = parentIn
  self.name = nameIn
end sub

and create new children like this:

sub AddAChildNamed (name as String)
  dim newChild as new Person (self, name)
  self.children.Append newChild
end sub

This is not optimal because you'd get circular references (parent references children who in turn reference back their parent). And since Xojo uses ref-counting for keeping its objects alive, and does not have a separate garbage collection task, removing all references from your main code to the top parent won't free all those Person objects, because they still keep referencing each others, thereby keeping themselves alive.

One solution would be to add a "FreeAllChildren" method that you'd have to call right before are ready to release the entire tree, but that's not very elegant (it's the fatest solution, though, if you get this right).

A more natural and fool-proof way is to use weak references for the child-to-parent connections, like this:

class Person
  property name as String
  property parent as WeakRef // **changed**
  property children() as Person
end class

sub Constructor (parentIn as Person, nameIn as String)
  self.parent = new WeakRef (parentIn)
  self.name = nameIn
end sub

To access the actual parent, you'd use code like this to temporarily re-create a hard reference to the parent object:

  dim myParent as Parent = Parent (self.parent.Value)

With the above changes, you won't have circular references any more.

However, it's not very efficient. If you have many 1000s of parent objects, you'll get as many WeakRef objects. And the downside of WeakRef is that it involves a search operation to locate the actual parent object when you use the WeakRef.Value function. And the more WeakRef objects you have, the more time it takes to look up these values.

Now consider this: Usually, with these parent-child relationships, there are more children to a parent than vice versa. In the above code, every child creates a WeakRef, often for the same Parent. And that's what we can optimize for:

Instead of having the child create its own WeakRef, let us have the parent provide it, as it'll remain constant.

Change the constructor to accept a WeakRef:

sub Constructor (parentRefIn as WeakRef, nameIn as String)
  self.parent = parentRefIn
  self.name = nameIn
end sub

add a new property to the class:

class Person
  property selfRef as WeakRef
  ...

and update the way a child gets added accordingly:

sub AddAChildNamed (name as String)
  if selfRef = nil then selfRef = new WeakRef (self)
  dim newChild as new Person (selfRef, name)
  self.children.Append newChild
end sub

And that's all.

TL;DR

If you use WeakRefs, and if you create many WeakRef for the same object, consider creating the WeakRef only once and cache it, to gain runtime performance.