A “million files” test

Writing a file manager is definitely a quite special kind of fun. Despite a seeming simplicity there’s a lot of details that should be considered when implementing it. Using efficient structures, algorithms and architecture can mean much, regardless that all remains under the hood and is not visible to user. Since the main purpose of a file management app is navigation between folders and showing their’s content, I’ve managed to perform some tests to show how different implementations can handle this (quite simple?) task. At the moment my collection of Mac OS X file managers was 11 different ones (all this software can be easily found in Google, also I don’t claim I’ve tested all file managers for Mac OS X – there’re others).
OK, to be precise – this is a stress test. By stress I mean not a usual stress, but STRESS.
The job is very simple: reading and showing a content of a directory with 1,000,000 files. Nothing more, just it. I’ve taken my old 8Gb USB stick, plugged it into my Macbook Pro running OS X Mavericks and formatted it into HFS+ journaled, also turned off Spotlight on this volume. Then run a tiny app, which I called fs_killer ūüôā
int main(int argc, const char * argv[]) {
    char tmp[MAXPATHLEN];
    for(int i = 0; i < 1000000; ++i) {
¬† ¬† ¬† ¬† sprintf(tmp, “/Volumes/test/%6.6d.txt”, i);
        close(open(tmp, O_WRONLY|O_CREAT, S_IRUSR|S_IWUSR|S_IRGRP));
    }
    return 0;
}

Here’s the test itself: run an app, check if it will be able to open this folder, record how much memory it has consumed and check if app is still usable (cursor movements and scrolling ability). Every app was given a plenty of time to load the directory listing, and this parameter wasn’t counted. The comparison table in alphabetical order is below:

Results
Application name Opened Memory Usable
DCommander yes ~1.7Gb yes
FastCommander yes ~1.1Gb yes
Nimble Commander yes 150Mb yes
Finder
yes
~2Gb yes
ForkLift yes ~1.7Gb yes
Macintosh Explorer yes ~1Gb yes
Midnight Commander yes 133Mb yes
Moroshka File Manager yes 160Mb no
Mover yes ~2Gb no
muCommander no n/a n/a
ZCommander yes 850Mb yes
A few words for conclusion. Two things can be clearly seen:
1) Midnight Commander (mc) is the winner (and the only to run in console) and muCommander is very bad – it was the only one to fail the opening test.
2) These file managers can be divided into 2 groups by memory consumption: less than roughly 200Mb and above it. I suppose this difference to be consequence of an internal data storage structure – while the first group relies on plain C / C++ memory management, the others use Objective C / Cocoa infrastructure to handle directory listing data, which is considerable less efficient in this aspect.
As the bottom line I can only give a link to Nimble Commander, it’s free now: http://magnumbytes.com/

File management and file system stuff

One can ask a reasonable question – why on earth do we need another file management app if we have Finder for example?
Funny, but there are many not-so-obvious motives, I’ll tell about one of them below.

Today’s reasoning is: file fragmentation.
Apple’s old HFS+ is of course bad and ugly (it was ugly in classic Mac OS, and is still ugly in Mac OS X), but it supports some of modern concepts such as extents.
Some reading can be found in Wikipedia:
http://en.wikipedia.org/wiki/HFS+
http://en.wikipedia.org/wiki/Extent_(file_systems)
http://en.wikipedia.org/wiki/File_fragmentation
In ideal situation, file can be described in file allocation table (any variant of it) with a single record, like position and length in cluster terms. It’s good for disk (especially for spinning drives), but it is also good for all file system logic, which is involved in file operations. The more extents is used for file allocation – the more logic overhead is later needed to operate with that file.

Now it’s time for experiment: copy a big file (OS X 10.9 distro) with Finder under OS X 10.8.4. My hard drive has a plenty of free space, by the way.
After it’s done just use a fancy tool fileXray to see what’s happened on file system layout level:

mbp:~ migun$ sudo su
Password:
sh-3.2# fileXray /Users/migun/!/OS X 10.9.dmg 
  path                 = Macintosh HD:/Users/migun/!/OS X 10.9.dmg
# Catalog File Thread Record
# Record 0 in node 48278 beginning at 512-byte sector 0x227170
  parentID             = 20404714
  nodeName             = OS X 10.9.dmg
# Catalog File Record
# Record 12 in node 62013 beginning at 512-byte sector 0xc77170
  type                 = file
  file ID              = 20405288
  flags                = 0000000010000010
                       . File has a thread record in the catalog.
                       . File has date-added stored in Finder Info.
  reserved1            = 0
  createDate           = Sun Jun 16 13:37:35 2013
  contentModDate       = Sun Jun 16 14:12:37 2013
  attributeModDate     = Tue Aug 20 10:03:55 2013
  accessDate           = Tue Aug 20 10:01:09 2013
  backupDate           = 0
  # BSD Info
  ownerID              = 501 (migun)
  groupID              = 20 (staff)
  adminFlags           = 00000000
  ownerFlags           = 00000000
¬† fileMode ¬† ¬† ¬† ¬† ¬† ¬† = -rw-r–r–¬†
  linkCount            = 1
  textEncoding         = 0
  reserved2            = 0
  # Finder Info
  fdType               = 0
  fdCreator            = 0
  fdFlags              = 0000000000000000
  fdLocation           = (v = 0, h = 0)
  opaque               = 0
  # Extended Finder Info
  reserved1            = 0
  date_added           = Tue Aug 20 10:01:09 2013
  extended_flags       = 0000000000000000
  reserved2            = 0
  reserved3            = 0
  # Data Fork
  logicalSize          = 4965827853 bytes (5.0 GB)
  totalBlocks          = 1212361
  fork temperature     = no record in Hot File B-Tree
  clumpSize            = 0
  extents              =   startBlock   blockCount      % of file

                            0x1a71af4        0x800         0.17 %
                            0x1c58c9f       0x1000         0.34 %
                            0x1c5c079       0x2000         0.68 %
                            0x1c5fe93       0x2000         0.68 %
                            0x1c64311       0x2000         0.68 %
                            0x1c918e8       0x2000         0.68 %
                            0x1c93b05       0x4000         1.35 %
                            0x1c9d8b8       0x2000         0.68 %

                            0x1ca5787       0x2000         0.68 %
                            0x1ca8689       0x4000         1.35 %
                            0x1cac6b2       0x2000         0.68 %
                            0x1d2efd2       0x2000         0.68 %
                            0x1ecdcaf       0x2000         0.68 %
                            0x215ce83       0x2000         0.68 %
                            0x215efab       0x4000         1.35 %
                            0x216325f       0x2000         0.68 %

                            0x2165512       0x2000         0.68 %
                            0x2167809       0x2000         0.68 %
                            0x2171a13       0x2000         0.68 %
                            0x2173a29       0x2000         0.68 %
                            0x2175ca9       0x2000         0.68 %
                            0x2179a62       0x2000         0.68 %
                            0x21c3fb2       0x2000         0.68 %
                            0x21c6cc1       0x2000         0.68 %

                            0x21c8cd1       0x2000         0.68 %
                            0x21cb1d4       0x2000         0.68 %
                            0x21d8aa0       0x2000         0.68 %
                            0x21dcff3       0x2000         0.68 %
                            0x21e936d       0x2000         0.68 %
                            0x21eb36e       0x2000         0.68 %
                            0x21ed371       0x2000         0.68 %
                            0x21ef7dc       0x2000         0.68 %

                            0x21f17df       0x6000         2.03 %
                            0x21f77e2       0x6000         2.03 %
                            0x21fd90a       0x2000         0.68 %
                            0x221fa99       0xe000         4.73 %
                            0x2237d36       0xc000         4.05 %
                            0x22884a4       0x4000         1.35 %
                            0x228c4a6       0x2000         0.68 %
                            0x229ccfb       0x2000         0.68 %

                            0x23e14b7       0x2000         0.68 %
                            0x23e35f4       0xe000         4.73 %
                            0x23f2ff7       0x2000         0.68 %
                            0x23f4ff9       0x2000         0.68 %
                            0x23f7126       0x2000         0.68 %
                            0x23f9127       0x2000         0.68 %
                            0x240e765       0x8000         2.70 %
                            0x242b007       0x2000         0.68 %

                            0x242d00a       0x6000         2.03 %
                            0x245c6b2       0x8000         2.70 %
                            0x24d0b58       0x2000         0.68 %
                            0x24d2e0b       0x8000         2.70 %
                            0x24db22b       0xc000         4.05 %
                            0x24e722c      0x10000         5.41 %
                            0x24f722d       0xa000         3.38 %
                            0x250122e      0x10000         5.41 %

                            0x25175f2       0x4000         1.35 %
                            0x251b5f3       0x2000         0.68 %
                            0x251d740       0x4000         1.35 %
                            0x2521747       0x6000         2.03 %
                            0x252774e       0x2000         0.68 %
                            0x2529997       0xa000         3.38 %
                            0x2533c49       0x2000         0.68 %
                            0x2535efc       0x4000         1.35 %

                            0x2539f00       0x4000         1.35 %
                            0x253e1b2       0x2000         0.68 %
                            0x254046c       0x6000         2.03 %
                            0x2546763       0x2000         0.68 %
                            0x25734b5       0x6000         2.03 %
                            0x25794b8       0x4000         1.35 %
                            0x257d5e2       0x4000         1.35 %
                            0x25815e5       0x6000         2.03 %

                            0x25875e7        0x7c9         0.16 %

                         1212361 allocation blocks in 73 extents total.
                         16607.68 allocation blocks per extent on an average.
  # Resource Fork
  logicalSize          = 0 bytes

File was allocated with 73 extents. Now try to do the same with Files manager:

sh-3.2# fileXray /Users/migun/!/OS X 10.9.dmg 
  path                 = Macintosh HD:/Users/migun/!/OS X 10.9.dmg
# Catalog File Thread Record
# Record 184 in node 18946 beginning at 512-byte sector 0x1b4830
  parentID             = 20404714
  nodeName             = OS X 10.9.dmg
# Catalog File Record
# Record 11 in node 62013 beginning at 512-byte sector 0xc77170
  type                 = file
  file ID              = 20408503
  flags                = 0000000010000010
                       . File has a thread record in the catalog.
                       . File has date-added stored in Finder Info.
  reserved1            = 0
  createDate           = Sun Jun 16 13:37:35 2013
  contentModDate       = Sun Jun 16 14:12:37 2013
  attributeModDate     = Tue Aug 20 10:25:18 2013
  accessDate           = Tue Aug 20 10:22:10 2013
  backupDate           = 0
  # BSD Info
  ownerID              = 501 (migun)
  groupID              = 20 (staff)
  adminFlags           = 00000000
  ownerFlags           = 00000000
¬† fileMode ¬† ¬† ¬† ¬† ¬† ¬† = -rw-r–r–¬†
  linkCount            = 1
  textEncoding         = 0
  reserved2            = 0
  # Finder Info
  fdType               = 0
  fdCreator            = 0
  fdFlags              = 0000000000000000
  fdLocation           = (v = 0, h = 0)
  opaque               = 0
  # Extended Finder Info
  reserved1            = 0
  date_added           = Tue Aug 20 10:22:10 2013
  extended_flags       = 0000000000000000
  reserved2            = 0
  reserved3            = 0
  # Data Fork
  logicalSize          = 4965827853 bytes (5.0 GB)
  totalBlocks          = 1212361
  fork temperature     = no record in Hot File B-Tree
  clumpSize            = 0
  extents              =   startBlock   blockCount      % of file

                            0xac38808      0x19000         8.45 %
                            0xad436aa      0x19000         8.45 %
                            0x24d2e0b      0x32000        16.89 %
                            0x26e1f5d      0x19000         8.45 %
                            0x2702f63      0x32000        16.89 %
                            0x2735846      0x19000         8.45 %
                            0x2a0ebc1      0x19000         8.45 %
                            0x2a4cc68      0x46fc9        23.98 %

                         1212361 allocation blocks in 8 extents total.
                         151545.12 allocation blocks per extent on an average.
  # Resource Fork
  logicalSize          = 0 bytes

After copying with Files manager the OS X 10.9 distro was allocated with 8 extents versus 73 when copied with Finder.¬†And that’s the today’s reason why you need a good alternative file manager.
Here’s the one: http://filesmanager.info/ ¬†ūüôā

Shairport bugs

To continue the previous post.
If you are getting a lot of nasty messages such as “missing frame”, “resending packet” and your sound is cracking sometimes – you’re welcome.

In the previous instruction the not-top version of shairport is fetched.
Go here to get the last version: https://github.com/albertz/shairport.

There were three bugs before (and two of them was fixed in github version). They all are related to hairtunes module.

1) (fixed on github) Function biquad_filt should be

static double biquad_filt(biquad_t *bq, double in) {
    double w = in Рbq->a[0]*bq->hist[0] Рbq->a[1]*bq->hist[1];
    double out = bq->b[1]*bq->hist[0] + bq->b[2]*bq->hist[1] + bq->b[0]*w;
    bq->hist[1] = bq->hist[0];
    bq->hist[0] = w;
    return out;
}
instead of

static double biquad_filt(biquad_t *bq, double in) {
    double w = in Рbq->a[0]*bq->hist[0] Рbq->a[1]*bq->hist[1];
    double out __attribute__((unused)) = bq->b[1]*bq->hist[0] + bq->b[2]*bq->hist[1] + bq->b[0]*w;
    bq->hist[1] = bq->hist[0];
    bq->hist[0] = w;
    return w;
}

2) (fixed on github) BUFFER_FRAME should be ^2 since sequence number is an unsigned short with overflowing. 512 works pretty well.

3) (not fixed on github) Nice bug in buffer_put_packet function:
Consider the following expression:
if (seqno == ab_write+1)
pretty simple piece of code, but there’s a bug here. Imagine the situation when seqno has overflowed already (eq 0) and ab_write is about to do it (eq 65535). In this case the expression above is NOT true.
ab_write+1 is automatically converted into int and so does seqno. So this expression actually looks like 0==65536, which is FALSE. The fix is quite fast:
if (seqno == (seq_t)(ab_write+1))
That’s all, have fun!

TP-Link TL-MR3020 as AirPlay receiver

WARNING!¬†The following post was written regarding MR3020 device. The author never used¬†WR703N nor tested the following steps to use Shairport on WR703N. Even more, it’s already known that the setup below may not work on¬†this device.

MR3020 is a nice box, which includes the following internals:

CPU: Atheros AR7240@400MHz
RAM: 32MiB
Flash: 4MiB
Lan: 1x100Mbit
WiFi: 802.11 b/g/n 150Mbps
SoC: Atheros AR9330 rev 1
USB: 1×2.0 (* notes below)
Serial: yes
JTAG: no
SoC: Atheros AR9330 rev 1
Power: 5V via mini-USB
OS: OpenWRT support
Very similar to TL-WR703N

That’s a quite powerful tiny box and it costs only 20-40$. That price makes MR3020 a very interesting one in terms of experimentation. I’ve decided to convert it into AirPlay receiver to push music stream¬†wirelessly¬†over the house.

My network config is something like this:
WIFI<——– dhcp client>MR3020<static 192.168.1.1/24 ——–>LAN (for administration reasons)
–>USB sound card–>audio cable etc
Since zeroconf works on broadcast basis we don’t need to know MR3020 address in WIFI network – it will be discovered and communicate automatically. So it’ll act as a usual DHCP client.

Here is the algo of such process and notes about pitfalls.
* Learn a bit about OpenWRT: http://openwrt.org/
* Read about router at OpenWRT site: http://wiki.openwrt.org/toh/tp-link/tl-mr3020
* Install a stock OpenWRT build into your device
* Set up a build environment. I’ve used Ubuntu 12.10 x64 running in VirtualBox
Here’s a good manual:¬†http://wiki.openwrt.org/doc/howto/buildroot.exigence
First of all you have to set up prerequisites depending on your build system.

* Download openwrt itself:
mkdir ~/openwrt
cd ~/openwrt
svn co svn://svn.openwrt.org/openwrt/trunk/
cd trunk

* Download and patch shairport package
copy feeds.conf.default to feeds.conf
add new source to the end: src-git jlars git://github.com/jlars/packages.git;master
checkout feeds:

./scripts/feeds update
./scripts/feeds install -a

* Patch shairport package:
cd feeds/jlars

wget -O Рftp://ftp.custom-openwrt-builds.info/patches/shairport_deps_trunk.diff | patch -p1
cd ~/openwrt/trunk

* Configure our build
select our target:
make menuconfig
select Target System->Atheros AR7xxx/AR9xxx
select Target Profile->TP-Link TL-MR3020

quit and fill the defaults:
make defconfig
enter menuconfig again check the following list of packages. MR3020 has only 4Mb flash, so system should contain only required packages (packages should be built into system – ‘y’ key to choose):

base-files
busybox
dropbear
hotplug2
mtd
swconfig
uci
kmod-leds-gpio
kmod-ledtrig-default-on
kmod-ledtrig-netdev
kmod-ledtrig-timer
kmod-ledtrig-usbdev
kmod-gpio-button-hotplug
kmod-wdt-ath79
kmod-sound-core
– all sound drivers
kmod-usb-audio
kmod-usb-ohci
kmod-usb2
kmod-ath9k
wpad-mini
shairport
uboot-envtools

* Try to build it
make -j 3 V=99

* Check if build was successful: check binary image at
bin/ar71xx/openwrt-ar71xx-generic-tl-mr3020-v1-squashfs-factory.bin
(
if you have weird errors while building sstrip tool – try to fix it’s makefile:
change this: $(HOSTCC) $(HOST_CFLAGS) -I../include -include endian.h $(HOST_STATIC_LINKING) -o $(HOST_BUILD_DIR)/sstrip src/sstrip.c
into this: $(HOSTCC) $(HOST_CFLAGS) $(HOST_STATIC_LINKING) -o $(HOST_BUILD_DIR)/sstrip src/sstrip.c
)

* Patch shairport on IPv6/iPv4 bug:
go into build_dir/target-mips_r2_uClibc-0.9.33.2/shairport-0.05/ and edit socketlib.c.
at line #162 comment out AF_INET6 option:
//    tFamily = AF_INET6;
build and install fixed version:
make package/shairport/compile
make package/shairport/install
make

* Now we need to edit configuration files so our build can start serving AirPlay right after installation.
FS root is located at: build_dir/target-mips_r2_uClibc-0.9.33.2/root-ar71xx
We need to edit 3 things:
– lan configuration
– wifi configuration
– shairport autostart

* Edit lib/functions/uci-defaults.sh
Locate things like this:

set network.lan=’interface’
set network.lan.ifname=’$ifname’
set network.lan.type=’bridge’
set network.lan.proto=’static’
set network.lan.ipaddr=’192.168.1.1′
set network.lan.netmask=’255.255.255.0′
and change them into this:

set network.lan=’interface’
set network.lan.ifname=’$ifname’
# set network.lan.type=’bridge’
set network.lan.proto=’static’
set network.lan.ipaddr=’192.168.1.1′
set network.lan.netmask=’255.255.255.0′
set network.wan=’interface’
set network.wan.proto=’dhcp’

Here we’re disabling bridging between lan and wifi and enable wifi(wan) with dhcp config.
* Edit lib/wifi/mac80211.sh
Locate things like this:
option type     mac80211
option channel  ${channel}
option hwmode 11${mode_11n}${mode_band}
$dev_id
$ht_capab
# REMOVE THIS LINE TO ENABLE WIFI:
option disabled 1
 
config wifi-iface
option device   radio$devidx
option network  lan
option mode     ap
option ssid     OpenWrt
option encryption none
and change them into this:

option type     mac80211
option channel  ${channel}
option hwmode 11${mode_11n}${mode_band}
$dev_id
$ht_capab
# REMOVE THIS LINE TO ENABLE WIFI:
# option disabled 1

config wifi-iface
option device   radio$devidx
option network  wan
option mode     sta
option ssid     YOUR_SSID
option encryption YOUR_ENCRYPTION
option key      YOUR_PASSWORD

write in the right configuration options of your WiFi network
* Edit etc/rc.local like this:
/usr/bin/shairport –apname=MR3020 –buffer=300 -d
exit 0

* Build the final image:
make target/install

* Find any lightweight http-server like Mangoose and share the system image located at bin/ar71xx/openwrt-ar71xx-generic-tl-mr3020-v1-squashfs-factory.bin
(better rename it into something like image.bin)

* Telnet into running MR3020 via cable at 192.168.1.1(it will root login without password) and install fresh image:
cd /tmp
wget http://192.168.1.2:8080/image.bin
mtd write image.bin firmware
reboot

After rebooting WiFi LED should be blinking and new AirPlay receiver named MR3020 will be available in your wireless network.
Pitfall note! MR3020 has USB2.0¬†_only_¬†port. That means that it will not work well with USB1.0/1.1 devices. There’s a pretty simple workaround – plug your sound card via USB2.0 hub. Here are details about this bug:¬†https://forum.openwrt.org/viewtopic.php?id=39956
Personally I’m using Creative USB Sound Blaster Play! (USB 1.1) and it works well with USB hub.

That’s all for now.