Posted on

8 bytes that’ll drive you mad

Today I’ve discovered a very strange bug in my software: after using an internal viewer in Files with PkgInfo in app package, Files crashes randomly and alerting on memory corruption.
Something like this:
Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
or this:
Files(85331,0x7fff7e8cc310) malloc: *** error for object 0x600000018a70: Heap corruption detected, free list canary is damaged
*** set a breakpoint in malloc_error_break to debug

A following story is below.


It was funny, since this viewer can easily handle a gigabyte-scale files. So I blamed the last refactoring and checked previous releases. They crash too, with the same symptoms.
Ok, I started investigations.
PkgInfo is 8-bytes file with text APPL????.
Copied this file to another place (some system-level locks maybe?) and viewed it. Crash.
Renamed file. Crash.
Created another 8-byte file with content 01234567 and tried it. Crash.
Created 7-byte and 9-byte files and tried them. Worked like a charm. Hmm…
It was something definitely related with alignment logic somewhere in low-level modules.
My suspicions fall onto data analysis module, which answers the questions like “what is the likely encoding for this bulk of data?” or “is this bulk of data binary or text?”.
Turned off this module and tried 8-byte file again. Crash.
Things becoming worse since sometimes viewer crashed even before it’s logic (layout, render, navigation etc) get to work.
Desperately I start tracking everything down from the very beginning of viewer’s initialization and came to my string decoders. At least it was a place where memory can become corrupted and I’ve changed encoding to Western (Mac OS Roman) from UTF-8 to see any difference. Worked like a charm. Hmm…
A few minutes later I finally stopped on relatively old UTF-8 conversion function:
void InterpretUTF8BufferAsIndexedUniChar(
const unsigned char* _input,
size_t _input_size,
unsigned short *_output_buf, // should be at least _input_size 16b words long
uint32_t *_indexes_buf, // should be at least _input_size 32b words long
size_t *_output_sz, // size of an output
unsigned short _bad_symb // something like ‘?’ or U+FFFD
)

And after tracing the decoding of 8 bytes “01234567” I finally stopped at a humble line:
    *_output_buf = 0;
}
That’s a zero-terminating of resulting UniChar buffer. But! -> // should be at least _input_size 16b words long
When looked into upper-level calling code there was a precise memory allocation for this buffer:
 m_DecodeBuffer = (UniChar*) calloc(m_FileWindow->WindowSize(), sizeof(UniChar));
So when file is 8-bytes long – the allocated memory is precisely 8 bytes long (when is was 7 or 9 bytes then allocation size was aligned onto some boundary and writing a zero-terminator didn’t cause any effect) and zeroing it (m_DecodeBuffer[8]=0) resulting in corruption of a following heap controlling structures, which causes a crash later.
Of course this zero-termination was unnecessary since every later function operating with UniChar buffer don’t rely on it’s zero-terminator.
The quest was complete.
Posted on

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/
Posted on

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 the 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 the 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 the ideal situation, a 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 the disk (especially for spinning drives), but it is also good for all file system logic, which is involved in file operations. The more extents are used for file allocation – the more logic overhead is later needed to operate with that file.

Now it’s time for an 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

The 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/  🙂