Posted on

C++: malloc/free/c pointers vs. new[]/delete[]/unique_ptr

One day I finally became tired of mallocing and freeing a memory by hand, and decided to move to modern c++ unique_ptr constructions. Is that more time-consuming under a  pressure? Absolutely not, and here is the synthetic test:

int main(int argc, const char * argv[])
{
    const size_t sizes_amount = 256;
    const size_t runs = 16*1024*1024;
    size_t sizes[sizes_amount];
    
    mt19937 mt((random_device())());
    uniform_int_distribution<size_t> dist(0, 1024*1024);
    for(auto &i: sizes)
        i = dist(mt);
    
    // test malloc/free and c pointers
    auto t0 = high_resolution_clock::now();
    for(int i = 0; i < runs; ++i) {
        void *v = malloc(sizes[i % sizes_amount]);
        /*Fake(v);use some empty fake function from another file so optimizer won’t throw this cycle away.*/
        free(v);
    }
    
    // test unique_ptr + new uint8_t[]
    auto t1 = high_resolution_clock::now();
    for(int i = 0; i < runs; ++i) {
        unique_ptr<uint8_t[]> v(new uint8_t[ sizes[i % sizes_amount] ]);
        /*Fake(v);use some empty fake function from another file so optimizer won’t throw this cycle away.*/
        v.reset();
    }
    
    auto t2 = high_resolution_clock::now();
    
    printf(“malloc/free + c pointers: %lldn”, duration_cast<milliseconds>(t1 – t0).count());
    printf(“new/detele + unique_ptr: %lldn”, duration_cast<milliseconds>(t2 – t1).count());
    
    return 0;
}

Results are quite promising, performance is just similar, with a much less error prone code:

malloc/free + c pointers new/detele + unique_ptr
5225 5200
5673 5427
5469 5653
5688 5624
6100 5497
5720 5640
5767 5854
5450 5626
5545 5631
5816 6199
Running on OSX Mavericks xnu-2422.1.72~6/RELEASE_X86_6, clang-500.2.78, -arch x86_64 -Os.
Posted on

Extracting extended attributes from Apple Double format

When files from native MacOSX filesystems (like HFS+) are copied to some storage that doesn’t support extended attributes (xattrs) natively, those attributes are not lost, instead they are placed in special files with a “._” prefix. For archives these paths may also contain “__MACOSX/” directory prefix.
These files have an ancient format called AppleDouble, which once was well documented but sadly lacks any support from current-gen Apple’s APIs.
Sometimes it’s necessary to work with such format, in my case – with compressed files inside zip archives. Ignoring separately-stored extended attributes may cause unwished consequences, mostly related with a user experience (invalid encodings, lost Finder’s labels etc) and is generally bad.
Here below is a code snippet which parses “._” file’s content and extracts a list of extended attributes with it’s data. This data may be passed to setxattr(..) function or be interpreted somehow. Some structures layout and functions are taken from Apple’s copyfile.c source.

Header (AppleDouble.h):
#pragma once
#include <stdint.h>
struct AppleDoubleEA
{
    // no allocations, only pointing at original memory buffer
    const void* data;
    const char* name; // null-terminated UTF-8 string
    uint32_t    data_sz;
   uint32_t    name_len; // length excluding zero-terminator. no zero-length names are allowed
};

/**
 * ExtractEAFromAppleDouble interprets a memory block of EAs packed into AppleDouble file, usually for archives.
 * Returns NULL or an array of AppleDoubleEA (number of _ea_count) allocated with malloc.
 * Caller is responsible for deallocating this memory.
 */
AppleDoubleEA *ExtractEAFromAppleDouble(const void *_memory_buf,
                                        size_t      _memory_size,
                                        size_t     *_ea_count
                                        );

Source file (AppleDouble.cpp):
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/xattr.h>
#include <libkern/OSByteOrder.h>
#include “AppleDouble.h”

#define ADH_MAGIC     0x00051607
#define ADH_VERSION   0x00020000
#define ADH_MACOSX    “Mac OS X        “
#define AD_DATA          1   /* Data fork */
#define AD_RESOURCE      2   /* Resource fork */
#define AD_REALNAME      3   /* File’s name on home file system */
#define AD_COMMENT       4   /* Standard Mac comment */
#define AD_ICONBW        5   /* Mac black & white icon */
#define AD_ICONCOLOR     6   /* Mac color icon */
#define AD_UNUSED        7   /* Not used */
#define AD_FILEDATES     8   /* File dates; create, modify, etc */
#define AD_FINDERINFO    9   /* Mac Finder info & extended info */
#define AD_MACINFO      10   /* Mac file info, attributes, etc */
#define AD_PRODOSINFO   11   /* Pro-DOS file info, attrib., etc */
#define AD_MSDOSINFO    12   /* MS-DOS file info, attributes, etc */
#define AD_AFPNAME      13   /* Short name on AFP server */
#define AD_AFPINFO      14   /* AFP file info, attrib., etc */
#define AD_AFPDIRID     15   /* AFP directory ID */
#define AD_ATTRIBUTES   AD_FINDERINFO
#define ATTR_HDR_MAGIC     0x41545452   /* ‘ATTR’ */
#define FINDERINFOSIZE 32

#pragma pack(1)
typedef struct apple_double_entry
{
u_int32_t   type;     /* entry type: see list, 0 invalid */
u_int32_t   offset;   /* entry data offset from the beginning of the file. */
u_int32_t   length;   /* entry data length in bytes. */
} apple_double_entry_t;

/* Entries are aligned on 4 byte boundaries */
typedef struct attr_entry
{
u_int32_t   offset;    /* file offset to data */
u_int32_t   length;    /* size of attribute data */
u_int16_t   flags;
u_int8_t    namelen;   /* length of name including NULL termination char */
u_int8_t    name[1];   /* NULL-terminated UTF-8 name (up to 128 bytes max) */
} attr_entry_t;

typedef struct apple_double_header
{
u_int32_t   magic;         /* == ADH_MAGIC */
u_int32_t   version;       /* format version: 2 = 0x00020000 */
u_int32_t   filler[4];
u_int16_t   numEntries;   /* number of entries which follow */
apple_double_entry_t   entries[2];  /* ‘finfo’ & ‘rsrc’ always exist */
u_int8_t    finfo[FINDERINFOSIZE];  /* Must start with Finder Info (32 bytes) */
u_int8_t    pad[2];        /* get better alignment inside attr_header */
} apple_double_header_t;

/* Header + entries must fit into 64K <– guess not true since 10.7 .MK. */
typedef struct attr_header
{
apple_double_header_t  appledouble;
u_int32_t   magic;        /* == ATTR_HDR_MAGIC */
u_int32_t   debug_tag;    /* for debugging == file id of owning file */
u_int32_t   total_size;   /* total size of attribute header + entries + data */
u_int32_t   data_start;   /* file offset to attribute data area */
u_int32_t   data_length;  /* length of attribute data area */
u_int32_t   reserved[3];
u_int16_t   flags;
u_int16_t   num_attrs;
} attr_header_t;
#pragma pack()

#define SWAP16(x) OSSwapBigToHostInt16(x)
#define SWAP32(x) OSSwapBigToHostInt32(x)
#define SWAP64(x) OSSwapBigToHostInt64(x)
#define ATTR_ALIGN 3L  /* Use four-byte alignment */
#define ATTR_DATA_ALIGN 1L  /* Use two-byte alignment */
#define ATTR_ENTRY_LENGTH(namelen)  
((sizeof(attr_entry_t) – 1 + (namelen) + ATTR_ALIGN) & (~ATTR_ALIGN))
#define ATTR_NEXT(ae)  
(attr_entry_t *)((u_int8_t *)(ae) + ATTR_ENTRY_LENGTH((ae)->namelen))

static const u_int32_t emptyfinfo[8] = {0};

/*
 * Endian swap Apple Double header
 */
static void
swap_adhdr(apple_double_header_t *adh)
{
   int count;
   int i;
    
   count = (adh->magic == ADH_MAGIC) ? adh->numEntries : SWAP16(adh->numEntries);
    
   adh->magic      = SWAP32 (adh->magic);
   adh->version    = SWAP32 (adh->version);
   adh->numEntries = SWAP16 (adh->numEntries);
    
   for (i = 0; i < count; i++)
   {
      adh->entries[i].type   = SWAP32 (adh->entries[i].type);
      adh->entries[i].offset = SWAP32 (adh->entries[i].offset);
      adh->entries[i].length = SWAP32 (adh->entries[i].length);
   }
}

/*
 * Endian swap extended attributes header
 */
static void
swap_attrhdr(attr_header_t *ah)
{
   ah->magic       = SWAP32 (ah->magic);
   ah->debug_tag   = SWAP32 (ah->debug_tag);
   ah->total_size  = SWAP32 (ah->total_size);
   ah->data_start  = SWAP32 (ah->data_start);
   ah->data_length = SWAP32 (ah->data_length);
   ah->flags       = SWAP16 (ah->flags);
   ah->num_attrs   = SWAP16 (ah->num_attrs);
}

static bool IsAppleDouble(const void *_memory_buf, size_t _memory_size)
{
    const apple_double_header_t *adhdr = (const apple_double_header_t *)_memory_buf;
    if(_memory_size < sizeof(apple_double_header_t) – 2 ||
       SWAP32(adhdr->magic) != ADH_MAGIC ||
       SWAP32(adhdr->version) != ADH_VERSION ||
       SWAP16(adhdr->numEntries) != 2 ||
       SWAP32(adhdr->entries[0].type) != AD_FINDERINFO
       )
        return false;
    
    return true;
}

AppleDoubleEA *ExtractEAFromAppleDouble(const void *_memory_buf,
                                        size_t      _memory_size,
                                        size_t     *_ea_count
                                        )
{
    if(!_memory_buf || !_memory_size || !_ea_count)
        return 0;
    
    if(!IsAppleDouble(_memory_buf, _memory_size))
        return 0;
    
    apple_double_header_t adhdr = *(const apple_double_header_t *) _memory_buf;
    swap_adhdr(&adhdr);
    
    bool has_finfo = memcmp(adhdr.finfo, emptyfinfo, sizeof(emptyfinfo)) != 0;
    
    AppleDoubleEA *eas = 0;
    int eas_last = 0;
    
    if(adhdr.entries[0].length > FINDERINFOSIZE)
    {
        attr_header_t attrhdr = *(const attr_header_t *)_memory_buf;
        swap_attrhdr(&attrhdr);
        
        if (attrhdr.magic == ATTR_HDR_MAGIC)
        {
            int count = attrhdr.num_attrs;
            eas = (AppleDoubleEA*) malloc( sizeof(AppleDoubleEA) * (has_finfo ? count + 1 : count) );
            
            const attr_entry_t *entry = (const attr_entry_t *)((char*)_memory_buf + sizeof(attr_header_t));
            for (int i = 0; i < count; i++)
            {
                if((char*)entry + sizeof(attr_entry_t) > (char*)_memory_buf + _memory_size)
                    break; // out-of-boundary guard to be safe about memory (not)corrupting
                
                u_int32_t offset = SWAP32(entry->offset);
                u_int32_t length = SWAP32(entry->length);
                u_int32_t namelen = 0;
                const char *name = (const char*)&entry->name[0];
                
                // safely calculate a name len
                for(const char *si = name; si < (char*)_memory_buf + _memory_size && (*si) != 0; ++si, ++namelen)
                    ;
                
                
                if(namelen > 0 &&
                   name + namelen < (char*)_memory_buf + _memory_size &&
                   name[namelen] == 0 &&
                   offset + length <= _memory_size)
                { // seems to be a valid EA
                    eas[eas_last].data = (char*)_memory_buf + offset;
                    eas[eas_last].data_sz = length;
                    eas[eas_last].name = name;
                    eas[eas_last].name_len = namelen;
                    ++eas_last;
                }
                entry = ATTR_NEXT(entry);
            }
        }
    }
    
    if(has_finfo)
    {
        if(!eas) // no extended attributes except FinderInfo was found
            eas = (AppleDoubleEA*) malloc( sizeof(AppleDoubleEA) );
        eas[eas_last].data = &((const apple_double_header_t *)_memory_buf)->finfo[0];
        eas[eas_last].data_sz = 32;
        eas[eas_last].name = XATTR_FINDERINFO_NAME; // “com.apple.FinderInfo”
        eas[eas_last].name_len = 20;
        ++eas_last;
    }
    
    *_ea_count = eas_last;
    
    return eas;
}

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/