Why does FUSE on Android suck?

Introduction

FUSE (Filesystem in Userspace) is a very useful mechanism in many applications. The thing is, those applications should not be focused on performance in terms of actual data transfers. FUSE has many advantages implied by userspace sandboxing, but for sure performance wasn't the main design consideration. I'm not telling that it is a bad design or something wrong with FUSE itself. It is just focused on other aspects like security, stability and easiness of creating applications. The problem I'd like to discuss here is that Google decided to use FUSE as a frontend to actual data stored on the non-volatile memory.

FUSE has been introduced in Android 4.4 to handle "emulated" storage. Before that, "emulated" storage path was mounted as VFAT. Here's how it looked on old ICS (output of mount command):

/dev/block/vold/179:14 /mnt/sdcard vfat rw,dirsync,nosuid,nodev,noexec,relatime,uid=1000,gid=1015,fmask=0702,dmask=0702,allow_utime=0020,codepage=cp437,iocharset=iso8859-1,shortname=mixed,utf8,errors=remount-ro 0 0

Don't be confused by "sdcard" directory name. It is still internal flash. External storage is usually mounted as something like "sdcard1".

This kind of partition was needed because of compatibility reasons. The applications can store data no matter if it's internal or external flash. In case of storing data on external SD cards, system has to deal usually with FAT32 filesystem. FAT32 is quite different than EXT4 used by Android internally. For instance, it's not case sensitive and doesn't handle discretionary access control.

Because of adding more Android specific permissions, Google decided to use FUSE to emulate FAT32:

/dev/fuse /mnt/shell/emulated fuse rw,nosuid,nodev,noexec,relatime,user_id=1023,group_id=1023,default_permissions,allow_other 0 0

FUSE

So, how does it work on Android?

First of all, there is a FUSE support enabled in kernel. Complementarily, there is a userspace daemon called "sdcard". On boot, the sdcard daemon mounts a /dev/fuse device to the emulated directory:

1743static int fuse_setup(struct fuse* fuse, gid_t gid, mode_t mask) {
1744    char opts[256];
1745
1746    fuse->fd = open("/dev/fuse", O_RDWR);
1747    if (fuse->fd == -1) {
1748        ERROR("failed to open fuse device: %s\n", strerror(errno));
1749        return -1;
1750    }
1751
1752    umount2(fuse->dest_path, MNT_DETACH);
1753
1754    snprintf(opts, sizeof(opts),
1755            "fd=%i,rootmode=40000,default_permissions,allow_other,user_id=%d,group_id=%d",
1756            fuse->fd, fuse->global->uid, fuse->global->gid);
1757    if (mount("/dev/fuse", fuse->dest_path, "fuse", MS_NOSUID | MS_NODEV | MS_NOEXEC |
1758            MS_NOATIME, opts) != 0) {
1759        ERROR("failed to mount fuse filesystem: %s\n", strerror(errno));
1760        return -1;
1761    }
1762
1763    fuse->gid = gid;
1764    fuse->mask = mask;
1765
1766    return 0;
1767}

After that, it polls on FUSE device waiting for messages from the kernel:

1581static void handle_fuse_requests(struct fuse_handler* handler)
1582{
1583    struct fuse* fuse = handler->fuse;
1584    for (;;) {
1585        ssize_t len = TEMP_FAILURE_RETRY(read(fuse->fd,
1586                handler->request_buffer, sizeof(handler->request_buffer)));
1587        if (len < 0) {
1588            if (errno == ENODEV) {
1589                ERROR("[%d] someone stole our marbles!\n", handler->token);
1590                exit(2);
1591            }
1592            ERROR("[%d] handle_fuse_requests: errno=%d\n", handler->token, errno);
1593            continue;
1594        }
(..)

Since now, every file operation inside directory mounted through FUSE will be handled in a specific way. For example, let's say we'd like to read file "test.txt" located at /sdcard/test.txt. Note again: "sdcard" means internal flash.

root@android: # cd /sdcard
root@android:/sdcard # cat test.txt

We expect cat to issue open(), read() and close() system calls during that operation. Let's have a look at what we get using strace:

root@android:/sdcard # strace -f -e open,openat,read,close cat test.txt
(..)
>>stripped output related to loading "cat" by shell<<
(..)                             = 0
openat(AT_FDCWD, "test.txt", O_RDONLY)  = 3
read(3, "1234\n", 1024)                 = 5
read(3, "", 1024)                       = 0
close(3)                                = 0

Looks ok, but hey, what is sdcard daemon doing in the meantime? Strace sdcard in the same time:

root@android: # ps | grep sdcard
media_rw  714   1     23096  1528  ffffffff 81ca6254 S /system/bin/sdcard
root@android: # strace -f -p 714 
Process 714 attached with 3 threads
[pid   916] read(3,  <unfinished ...>
[pid   915] read(3,  <unfinished ...>
[pid   714] read(4,  <unfinished ...>
[pid   916] <... read resumed> "1\0\0\0\1\0\0\0\2\234\3\0\0\0\0\0\200\200@\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 49
[pid   916] faccessat(AT_FDCWD, "/data/media/0/test.txt", F_OK) = 0
[pid   916] newfstatat(AT_FDCWD, "/data/media/0/test.txt", {st_mode=S_IFREG|0664, st_size=5, ...}, AT_SYMLINK_NOFOLLOW) = 0
[pid   916] writev(3, [{"\220\0\0\0\0\0\0\0\2\234\3\0\0\0\0\0", 16}, {"\200\261\317\200\177\0\0\0\223(\0\0\0\0\0\0\n\0\0\0\0\0\0\0\n\0\0\0\0\0\0\0"..., 128}], 2) = 144
[pid   915] <... read resumed> "0\0\0\0\16\0\0\0\3\234\3\0\0\0\0\0\200\261\317\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 48
[pid   916] read(3,  <unfinished ...>
[pid   915] openat(AT_FDCWD, "/data/media/0/test.txt", O_RDONLY|O_LARGEFILE) = 5
[pid   915] writev(3, [{" \0\0\0\0\0\0\0\3\234\3\0\0\0\0\0", 16}, {"\260p\300\200\177\0\0\0\0\0\0\0\0\0\0\0", 16}], 2 <unfinished ...>
[pid   916] <... read resumed> "P\0\0\0\17\0\0\0\4\234\3\0\0\0\0\0\200\261\317\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 80
[pid   915] <... writev resumed> )      = 32
[pid   916] pread64(5,  <unfinished ...>
[pid   915] read(3,  <unfinished ...>
[pid   916] <... pread64 resumed> "1234\n", 4096, 0) = 5
[pid   916] writev(3, [{"\25\0\0\0\0\0\0\0\4\234\3\0\0\0\0\0", 16}, {"1234\n", 5}], 2) = 21
[pid   915] <... read resumed> "8\0\0\0\3\0\0\0\5\234\3\0\0\0\0\0\200\261\317\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 56
[pid   916] read(3,  <unfinished ...>
[pid   915] newfstatat(AT_FDCWD, "/data/media/0/test.txt", {st_mode=S_IFREG|0664, st_size=5, ...}, AT_SYMLINK_NOFOLLOW) = 0
[pid   915] writev(3, [{"x\0\0\0\0\0\0\0\5\234\3\0\0\0\0\0", 16}, {"\n\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\224(\0\0\0\0\0\0\5\0\0\0\0\0\0\0"..., 104}], 2) = 120
[pid   916] <... read resumed> "@\0\0\0\31\0\0\0\6\234\3\0\0\0\0\0\200\261\317\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 64
[pid   916] write(3, "\20\0\0\0\0\0\0\0\6\234\3\0\0\0\0\0", 16) = 16
[pid   916] read(3, "@\0\0\0\22\0\0\0\7\234\3\0\0\0\0\0\200\261\317\200\177\0\0\0\0\0\0\0\0\0\0\0"..., 262224) = 64
[pid   916] close(5)                    = 0
[pid   916] write(3, "\20\0\0\0\0\0\0\0\7\234\3\0\0\0\0\0", 16) = 16
[pid   916] read(3,  <unfinished ...>
[pid   915] read(3, ^CProcess 714 detached
Process 915 detached

A lot is happening. This is because each file operation will now work in a following way:

1. Userspace application issues system call that will be handled by FUSE driver in kernel (we see it in the first strace output)
2. FUSE driver in kernel notifies userspace daemon (sdcard) about new request
3. Userspace daemon reads /dev/fuse
4. Userspace daemon parses command and recognizes file operation (ex. open)
5. Userspace daemon issues system call to the actual filesystem (EXT4)
6. Kernel handles physical data access and sends data back to the userspace
7. Userspace modifies (or not) data and passes it through /dev/fuse to kernel again
8. Kernel completes original system call and moves data to the actual userspace application (in our example cat)

Uff, that's a lot, isn't it? 

Performance

Let's see what side effects such attitude has. The obvious one is performance overhead for each additional system call. Here are numbers (all tests were performed several times, each time similar results were observed):

Test #1: Copy big file within one partition.

EXT4 FS:

root@android:/data # echo 3 > /proc/sys/vm/drop_caches
root@android:/data # dd if=bigbuck.in of=bigbuck.out bs=1m                      
691+1 records in
691+1 records out
725106140 bytes transferred in 10.779 secs (67270260 bytes/sec)

FUSE:

root@android:/sdcard # echo 3 > /proc/sys/vm/drop_caches                      
root@android:/sdcard # dd if=bigbuck.in of=bigbuck.out bs=1m                  
691+1 records in
691+1 records out
725106140 bytes transferred in 13.031 secs (55644704 bytes/sec)

RESULT:

In this test, FUSE is about 17% slower.

Test #2: Copy a lot of small files within one partition. There were 10 000 files each one 5kB of size.

EXT4 FS:

root@android:/data # echo 3 > /proc/sys/vm/drop_caches
root@android:/data # time cp small/* small2/                                  
    0m17.27s real     0m0.32s user     0m6.07s system

FUSE:

root@android:/sdcard # echo 3 > /proc/sys/vm/drop_caches                      
root@android:/sdcard # time cp small/* small2/                                
    1m3.03s real     0m1.05s user     0m9.59s system

RESULT:

I think the comment is superfluous. It took over 1 minute (!) to copy ~50MB of small files on FUSE mounted partition in comparison to ~17 seconds on EXT4 FS.

Double caching

Another implication is double caching of data.  Linux Kernel uses page cache mechanism to store recently accessed data in memory, specifically data from a non-volatile storage. This greatly improves data access performance. However, we don't want to have the same data cached twice. Unfortunately, this will happen because of the way in which FUSE is used on Android.

Observing double caching behavior caused by FUSE is very simple:

1. Create file with a known size
2. Copy it into /sdcard folder on the phone (/sdcard is a symlink to /storage/emulated/legacy which is a symlink to /mnt/shell/emulated/0 which is mounted as FUSE)
3. Drop page cache -> take a snapshot of page cache usage -> read test file -> take another snapshot of page cache -> see a difference between page cache usage before and after reading the file:

root@android: # echo 3 > /proc/sys/vm/drop_caches ; sleep 1 ; cat /proc/meminfo | grep Cache ; cat /sdcard/test_file > /dev/null ; cat /proc/meminfo | grep Cache

If size of the file is for example 10MB we'll get something like this:

before file operation:  

Cached: 241864 kB

after file operation: 

Cached: 263072 kB

Expected result would be 10MB more than 241MB in cache, so something around 251MB. Instead, we see 263MB in cache after reading 10MB of data. It means kernel cached twice as needed. The same test performed directly on EXT4 FS (for instance in /data folder) will show, as expected, 10MB more of cached pages.

So, we have the same data cached twice. Once as a user application that issued original open/read system call and once as "sdcard" daemon. First data is cached by FUSE, second one by EXT4 FS.

When I first noticed it I tried to force FUSE to skip caching. Here are my notes from that time:

We can skip fuse cache by providing FOPEN_DIRECT_IO inside kernel. I tested this solution, however it affected performance significantly. Although caching works ok (meaning there is only one copy of data in cache and subsequent reads doesn't generate i/o to the flash) there is additional overhead for switching more often between sdcard daemon and fuse fs in kernel. Maybe it can be tweaked more.
There is FOPEN_KEEP_CACHE in fuse that might be useful – it needs more investigation.
Other solution is to provide O_DIRECT flag in sdcard daemon when it's opening ext4fs files. We then discard caches from ext4fs and we should be able to use page cache created by fuse. However, using O_DIRECT requires user buffers to be aligned in memory to the block size. Also the size of data chunks should be aligned. Sdcard daemon is prepared for external O_DIRECT requests by Google:
https://android-review.googlesource.com/#/c/82141/4/
https://android-review.googlesource.com/#/c/82570/ . The possible solution would be to enable KEEP_CACHE in Fuse on kernel side and use O_DIRECT to all sdcard daemon requests. I did it for ‘read’ case and it works, however there is a significant overhead for the first read of data. Subsequent reads are much faster than originally (due to caching in fuse). Using it for writes may be tricky though.
Another way to solve it is to provide POSIX_FADV_DONTNEED fadvise in sdcard dameon. I tested it as well, however again - it affects performance too much.

Basically, the most important conclusion from above investigation was: get rid of FUSE and implement FAT32 emulation layer inside kernel.

Other issues

Beside performance and double caching, there are other problems with FUSE on Android. For instance, not all features from FAT32 are implemented in sdcard daemon. There were issues with utime() system call and with lack of full support for O_DIRECT flag.

I don't want to blame Google only. As officialy stated:

"Devices may provide external storage by emulating a case-insensitive, permissionless filesystem backed by internal storage. One possible implementation is provided by the FUSE daemon in system/core/sdcard, which can be added as a device-specific init.rc service". 

FUSE daemon is only example implementation that is easiest to maintain, but it has also a lot of drawbacks.
What's more interesting, some mobile vendors (Samsung, Motorola) have already realized it and replaced FUSE with their own in-kernel (or mixed) implementation. Samsung has created driver based on WrapFS called "sdcardfs". In my opinion it's the best approach: use WrapFS to implement FAT32 emulation layer inside kernel. If Samsung implemented it correctly it's another question, but from what I saw in officially published Samsung kernel sources it's not so bad.

Summary

To sum-up why does FUSE on Android suck:

• Performance
• Double caching
• Several other minor defects, like missing allow_utime flag

Note, Android as an operating system doesn't access files via FUSE internally. However, high-level applications do. Use cases like saving photos from camera, recording videos or reading offline maps will suffer the most from FUSE drawbacks described in this article. 

Android: memory management insights, part I

TLDR:

Article is a series of Linux memory management experiments. Author realizes that allocating memory on stack is equivalent to just moving Stack Pointer and that acquiring dynamic memory means using brk() or mmap() system calls. Also, the overcommit mechanism has been presented.


Introduction

This article is about how memory allocation works on ARM based Android OS. Android uses modified Linux Kernel, however some of the patches specific to Android are already in the mainline. The list of Kernel features added by Android can be found here. We see there components such as Binder (interprocess communication mechanism and the remote method invocation system), Ashmem (Android shared memory), Logger (kernel part of logcat), Wakelocks (used for power management), Out of Memory handling (lowmemorykiller).
From memory management perspective, Android uses standard Linux Kernel mechanisms with addition of custom out-of-memory handling. One more thing worth noticing is Android-based devices usually don't have swap partition. This means all standard Kernel features related to swapping memory into non-volatile storage are not in use. The exception is when zRAM features are enabled. zRAM is usually enabled on latest Android devices with less than 1GB of RAM. Currently zRAM is not in scope of this article.
From userspace point of view, Android uses Bionic as standard C library. Up to Kitkat dlmalloc was used as a default malloc() implementation. From Lollipop it is the jemalloc. On top of the native part there is a Java virtual machine (although not officially “JVM “due to license reasons) implementation called ART (until L it was Dalvik) with its own managed heap.

The ultimate purpose of this article is to track by examples the memory allocation process up from Dalvik/ART through malloc() and Linux Kernel down to MMU of the processor. Insight of what's happening under the hood should help with understanding memory usage, memory leaks and memory corruptions.

There is a lot of abstraction layers to traverse but lets start in the middle of the road which is a native userspace memory allocation. This means we'll firstly look how a native application can acquire some memory without help of standard C library or any specific malloc() implementation.

Virtual memory

We'll start with creating a reference template program and we'll gradually add more features to see how it affects OS internals. We'll use GCC ARM Embedded toolchain and add the '''-nostdlib''' flag to linker:

$>arm-eabi-gcc -nostdlib -O0 test_app.c -o test_app

Here is our first program:

1 2 3 4

void main() { while(1); }

Using objdump we can take a look into generated asm:

$>arm-eabi-objdump -d test_app

test_app:     file format elf32-littlearm

Disassembly of section .text:

00008000 <main>:
    8000: e52db004  push {fp}  ; (str fp, [sp, #-4]!)
    8004: e28db000  add fp, sp, #0
    8008: eafffffe  b 8008 <main+0x8>

Beside expected branch instruction (the infinite loop) we can see two additional instructions related to the maintenance of the frame pointer. We'll discuss FP later while explaining how the stack works.

For now, we don't have any variables, so after running our program not so much about memory allocation will happen despite loading the actual code into the memory. We'll not discuss loading ELF file into memory at this point.
Note, we're not using startup files from stdlib, so we have a starting point of our program defaulted to 0x00008000 which is the beginning of .text section. We're informed about this during linking;

“arm-eabi/bin/ld: warning: cannot find entry symbol _start; defaulting to 0000000000008000” 

At the beginning of .text section our main() function resides. This is why we don't need to explicitly set the _start symbol for now. If you want to get rid of this warning, just rename main() to _start().

Let's run the program and inspect the actual memory layout that is created by Kernel for our process. At this point, lets quickly recap what actually is a virtual address space of the process. For detailed information you can refer to the Linux Kernel Development by Robert Love or to Anatomy of a program in memory (this is actually a highly recommended reading). In short words: every time the new process is spawned, Kernel “creates” for it a kind-of sandbox of virtual addresses range in which the process operates (performs reads, writes or executes the code). “Creates” means allocates and initialize its internal structures describing the process (for example task_struct, vm_area_struct, mm_struct). On 32bit architecture, each process could have an address space ranging from 0x00000000 to 0xFFFFFFFF. However for performance reasons Kernel needs to has its own mapping available no matter what process is scheduled on. It depends on Kernel configuration how much of the virtual space Kernel needs. Standard split is “3:1” which means that from 4GB address space of 32bit architecture, 3GB is dedicated for userspace program and 1GB is always mapped for Kernel use. That leaves us with addresses from 0x00000000 to 0xbfffffff available for userspace. Anything above cannot be accessed by userspace program. There are exceptions however of this restriction: VDSO and/or ARM Kernel User Helpers which are special mappings that userspace can use for performance purposes (mostly because of userspace implementation of system calls like gettimeofday() or clock_gettime()).
The virtual address space available for user space process (so up to 0xbfffffff) is logically divided into different sections with different permissions. Example section can be a read-only, executable .text or read-write .heap. Because actual data is stored in the physical memory at some point we of course need to do a transition from the virtual address to the physical address. Transition is done with use of structures called page tables.  The page tables are architecture-specific and their location must be provided to MMU during initialization of the system. Page tables are also cached in a TLB of the MMU to speedup access to the given mapping. Every time the process is scheduled by Kernel, the whole address space for the process is switched, which means that processor needs to use a different page table while accessing memory. Later we'll explain more about access to the physical memory. For now, we should assume that each virtual address '''can''' (but not necessarily for all the time) refer to the address in the underlying physical memory and the transition is handled transparently by the OS.

Lets run our program and look into the example virtual space. We can get needed information from /proc/<pid>/maps and for more detailed view from /proc/<pid>/smaps. Note, all commands are performed on ARM based Android device, not on a host machine.

Example of /proc/<pid>/maps:

00008000-00009000 r-xp 00008000 b3:1a 24439      /data/test_app 
b6f98000-b6f99000 r-xp 00000000 00:00 0          [sigpage] 
be7eb000-be80c000 rwxp 00000000 00:00 0          [stack] 
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors]

Corresponding /proc/<pid>/smaps:

00008000-00009000 r-xp 00008000 b3:1a 24439      /data/test_app 
Size:                  4 kB 
Rss:                   4 kB 
Pss:                   4 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         4 kB 
Private_Dirty:         0 kB 
Referenced:            4 kB 
Anonymous:             0 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB 
b6f98000-b6f99000 r-xp 00000000 00:00 0          [sigpage] 
Size:                  4 kB 
Rss:                   0 kB 
Pss:                   0 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB 
Private_Dirty:         0 kB 
Referenced:            0 kB 
Anonymous:             0 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB 
be7eb000-be80c000 rwxp 00000000 00:00 0          [stack] 
Size:                136 kB 
Rss:                   4 kB 
Pss:                   4 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB 
Private_Dirty:         4 kB 
Referenced:            4 kB 
Anonymous:             4 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB 
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors] 
Size:                  4 kB 
Rss:                   0 kB 
Pss:                   0 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB 
Private_Dirty:         0 kB 
Referenced:            0 kB
Anonymous:             0 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB

Above output will be our reference memory layout. After playing around with the memory allocation we'll see how additional sections appear, how and when the memory usage is changing.  This is our starting point. Let's explain then what we see so far.

After running the program we see in /proc/maps 4 virtual memory areas:

• data/test_app : it is our .text section (set of processor instructions)
• [sigpage]: a special mapping for signal handling.
• [stack] : virtual memory area reserved for the program stack. Each local variable will use this space as a memory, some arguments and registers (especially LR) will be also stored here. It grows downward (so the SP is firstly around be80c000 in our example) and its size can be increased (for userspace processes) by Kernel up to RLIMIT_STACK.
• [vectors]: Processor exception table is mapped here. Also it's used by the special mechanism called “ARM Kernel User Helpers”. You can refer to Kernel documentation for more details about it.

We don't have global variables, memory-mapped files or dynamic allocation on the heap so far.

Next, we've inspected smaps. Example output looks like this (VM area of the process' stack area):

be7eb000-be80c000 rwxp 00000000 00:00 0          [stack]
Size:                136 kB
Rss:                   4 kB
Pss:                   4 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         4 kB
Referenced:            4 kB
Anonymous:             4 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB

Now, we can go through each field and explain what it's telling us.

• Size – It's a virtual memory size of the area. In above example you can subtract 0xbe7eb000 from 0xbe80c000 to get this value. It is also called “vss” - virtual set size . It's a total virtual space accessible by this area and it is '''not''' related to RAM usage at all (or nearly at all). In worst case (when we physically allocate it fully), the RAM usage will be equal to this value, so it's an upper limit. However, this value can change at runtime, for example when the stack grows or we add memory mapped files.  We'll see later how to allocate this Virtual memory and why Vss is not good for determining memory usage.
• Rss – Resident set size, it's the total memory actually held in RAM. It doesn't distinguish between shared and private memory. This means, that not only this particular process is using memory reported by RSS but also other processes can use part of this memory.
• Pss – Proportional set size. Quoting from lwn.net: “The "proportional set size" (PSS) of a process is the count of pages it has in memory, where each page is divided by the number of processes sharing it. So if a process has 1000 pages all to itself, and 1000 shared with one other process, its PSS will be 1500. “

At this point, we should mention that from the Kernel memory management perspective, the smallest managed unit is called page. In most Android platforms (32bit ARM) the page size is 4KB. Userspace program cannot request from OS less than page_size of the memory.

Before explaining next fields we need to know about kernel page cache mechanism. If some data is read from a non-volatile storage it is cached (buffered) in the RAM, so each next read is done from RAM not from the non-volatile storage. This is of course possible until we modify that data. If the underlying page is not modified, then it has flag “clean”. If the page has been written, it has flag “dirty”. When the system (or user) performs sync() operation, dirty pages from caches are written physically into the storage.
Note, Kernel holds information about each physical page of the system in the global mem_map variable, which is an array of structures called page. You can take a look on declaration of struct page at kernel/include/linux/mm_types.h.

Getting back to the output of smaps:

• Shared_Clean– How many shared pages are marked as “clean” (not modified). "Shared" means the physical page can be mapped by more than one process. Example can be a code of shared library.
• Shared_Dirty – The same as above, but page has been modified.
• Private_Clean – How many private pages are marked as “clean”. Private page is accessible only by given process.
• Private_Drity – The same as above, but page has been modified. Note: page doesn't need to be a part of cache mechanism to be marked as dirty. All pages modified in RAM become “dirty” no matter if it's a memory-mapped file or anonymous page. In case of anonymous pages they can be “clean” only if they were no modified at all (so for example they are marked as read-only).
• Referenced – Number of pages that have been referenced since last LRU list enqueue/requeue. This field is related to Page Frame Reclamation mechanism, which in Android devices is not important because usually there is no swap.
• Anonymous – How many pages are marked as “anonymous”, which means there is no underlying file to which given page is mapped.
• AnonHugePages – This field is related to Huge Pages mechanism. It's not valid for most Android devices.
• Swap – as mentioned before, also not valid for most Android devices.
• KernelPageSize – Size of the page managed by Kernel. It's a constant value, usually 4KB.
• MMUPageSize – Page size on which operates MMU.
• Locked – Number of pages that are exclusively locked, so they cannot be swapped.  Pages can be locked and unlocked by mlock() and munlock() calls.

Global variables

We'll now add couple of different global variables and see in what sections they will be stored:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

static int a; int b; static int c = 12345; int d = 3333; static char tmp[24] = "TEST"; void main() { static int e; static int f = 666; while(1); }

This is how new symbols appear in ELF:

arm-eabi-nm test_app
00010030 b a   <--
00010038 B b   <--
0001003c B __bss_end__
0001003c B _bss_end__
00010030 B __bss_start
00010030 B __bss_start__
0001000c d c  <--
00010010 D d  <--
0001000c D __data_start
00010034 b e.4064 <--
00010030 D _edata
0001003c B _end
0001003c B __end__
0001002c d f.4065 <--
00008000 T main
00080000 N _stack
         U _start
00010014 d tmp <--

“nm” shows offset of the symbol in ELF file, type of the symbol and name of the symbol. If symbol type is uppercase then symbol is global (external). If it's lowercase then it's local (not exported) symbol. We can see that static variables are local ones and not initialized global variables are stored in .bss section.  After loading and running the program we can observe following virtual memory map:

oot@D6503:/proc/8189 # cat maps
00008000-00009000 r-xp 00008000 b3:19 210        /data/test_app
00010000-00011000 rwxp 00008000 b3:19 210        /data/test_app <-- new one
b6f40000-b6f41000 r-xp 00000000 00:00 0          [sigpage]
be887000-be8a8000 rwxp 00000000 00:00 0          [stack]
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors]

We see additional section in which our variables are placed. Here are details of this mapping:

00010000-00011000 rwxp 00008000 b3:19 210        /data/test_app
Size:                  4 kB
Rss:                   4 kB
Pss:                   4 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         4 kB
Referenced:            4 kB
Anonymous:             4 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB

Stack

Firstly, we need to quickly describe so-called frame pointer. The stack pointer is saved into frame pointer each time the function is called, so frame pointer can be used as a reference for accessing local variables. The compiler however can generate code without use of frame pointer (-fomit-frame-pointer gcc option). If frame pointer is not used, then compiler needs to track the stack in other way. It depends on the architecture if it can be done other way or not (or how costly it is). In ARM mode the R11 is used as FP and in Thumb it's a R7. Sometimes (refer to gcc manual for more details) there is no possibility to omit the FP at all. In ARM however it's possible to not use a frame pointer (so the R11 can be utilized for other general purposes). FP is also used by debuggers and postmortem-analysis tools, so on some architectures disabling FP will make debugging impossible.

Here is an example program to show how stack works on ARM. Since we have more functions, we created symbol _start instead of main() to tell compiler where our entry point is. Otherwise it would start execution from the top-most function (in our example foo):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

static int foo(int a, int b, int c) { int d = a + b + c; int e = d * 2; return d; } static int bar(int a, int b, int c, int d, int e, int f, int g) { int h = a + b + c + d + e + f + g; int i; i = foo(a, h, g); return i; } static void wrapper() { int a = 4; int buf[24]; bar(a, 2, 3, 4, 5, 6, 7); return; } void _start() { wrapper(); while(1); }

To get general idea how stack works, read firstly Journey to the stack.
To run our test program through GDB you should issue following commands (assuming test_app is pushed into /data/):

on target:
gdbserver :5039 /data/test_app
on host:
adb forward tcp:5039 tcp:5039
gdbclient test_app
nice to set in GDB:
display/i $pc

you can then step instruction-by-instruction with si command

After running our program through GDB we can see in /proc/<pid>/maps our stack area starting (for example, because this address is randomized) at 0xbe9b2000 and ends at 0xbe9d3000:

be9b2000 - be9d3000 rwxp 00000000 00:00 0          [stack]

Type “info registers” in GDB to see where the SP is just after running the program:

(gdb) info registers
r0             0x0 0
r1             0xbe9d2a17               ← points to argv[0]
r2             0xbe9d2a22               ← points to argv[1] (if present)
r3             0x0 0
r4             0x0 0
r5             0x0 0
r6             0x0 0
r7             0x0 0
r8             0x0 0
r9             0x0 0
r10            0x0 0
r11            0x0 0
r12            0x0 0
sp             0xbe9d28f0               ← points to argc
lr             0x0 0               ← link register
pc             0x8114 0x8114 <_start> ← program counter
cpsr           0x10 16              ← Program status register

As we see, SP is not placed directly at the top of the .stack area. This is because at the beginning of  stack (don't forget it grows downwards) Kernel places environment variables and arguments passed to the program. Example:

(gdb) x/64sb 0xbe9d2a17
0xbe9d2a17: "test_stack"
0xbe9d2a22: "testarg1"
0xbe9d2a2b: "testarg2"
0xbe9d2a34: "_=/system/bin/gdbserver"
0xbe9d2a4c: "PATH=/sbin:/vendor/bin:/system/sbin:/system/bin:/system/xbin"
0xbe9d2a89: "LOOP_MOUNTPOINT=/mnt/obb"
0xbe9d2aa2: "ANDROID_ROOT=/system"
0xbe9d2ab7: "SHELL=/system/bin/sh"
0xbe9d2acc: "ANDROID_ASSETS=/system/app"
0xbe9d2ae7: "TERM=vt100"
0xbe9d2af2: "ANDROID_PROPERTY_WORKSPACE=10,0"
0xbe9d2b12: "ANDROID_BOOTLOGO=1"
0xbe9d2b25: "HOSTNAME=D6503"
0xbe9d2b34: "ANDROID_DATA=/data"
0xbe9d2b47: "BOOTCLASSPATH=/system/framework/core-libart.jar:/system/framework/conscrypt.jar:/system/framework/okhttp.jar:/system/framework/core-junit.jar:/system/framework/bouncycastle.jar:/system/framework/ext.j"...
0xbe9d2c0f: "ar:/system/framework/framework.jar:/system/framework/telephony-common.jar:/system/framework/voip-common.jar:/system/framework/ims-common.jar:/system/framework/mms-common.jar:/system/framework/android."...
0xbe9d2cd7: "policy.jar:/system/framework/apache-xml.jar:/system/framework/qcmediaplayer.jar:/system/framework/WfdCommon.jar:/system/framework/oem-services.jar:/system/framework/org.codeaurora.Performance.jar:/sys"...
0xbe9d2d9f: "tem/framework/vcard.jar:/system/framework/tcmiface.jar:/system/framework/com.xxxyyy.uxp.jar"
0xbe9d2e01: "EMULATED_STORAGE_SOURCE=/mnt/shell/emulated"
0xbe9d2e2d: "ANDROID_SOCKET_adbd=11"
0xbe9d2e44: "EMULATED_STORAGE_TARGET=/storage/emulated"
0xbe9d2e6e: "ANDROID_STORAGE=/storage"
0xbe9d2e87: "MKSH=/system/bin/sh"
0xbe9d2e9b: "EXTERNAL_STORAGE=/storage/emulated/legacy"
0xbe9d2ec5: "LD_PRELOAD=libsigchain.so:libNimsWrap.so"
0xbe9d2eee: "EXTERNAL_STORAGE_USB=/storage/usbdisk"
0xbe9d2f14: "RANDOM=5811"
0xbe9d2f20: "ASEC_MOUNTPOINT=/mnt/asec"
0xbe9d2f3a: "SECONDARY_STORAGE=/storage/sdcard1"
0xbe9d2f5d: "USER=root"
0xbe9d2f67: "HOME=/data"
0xbe9d2f72: "SYSTEMSERVERCLASSPATH=/system/framework/services.jar:/system/framework/ethernet-service.jar:/system/framework/wifi-service.jar"
0xbe9d2ff1: "test_stack"
0xbe9d2ffc: ""

Quick note about CPSR: it's a Current Program Status Register and it contains condition code flags, interrupt disable bits, current processor mode, and other status and control information. Refer to ARM ARM for more details. In our example CPSR has value “16” which means “processor mode is >>User<<”.

Lets proceed with our program and observe SP, FP and the stack content. We'll also look into ARM procedure call standard a little (how parameters are passed and where the return value is stored).

=> 0x00008114 <+0>: push {r11, lr}
   0x00008118 <+4>: add r11, sp, #4
   0x0000811c <+8>: bl 0x80c8 <wrapper>

(note, R11 is a FP)

This is the simplest example – function without arguments or return value. In such case the Link Register and previous Frame Pointer are firstly written to the stack and the FP is then set to SP plus 4.

Here's how the memory around SP looks before issuing any instruction of our program:

After pushing two values SP is automatically set to 8 bytes (two words) lower:

Next instruction:

add r11, sp, #4

writes 0xbe9d28ec to r11, so it points to the beginning of the stack frame (usually where LR is stored - for now it's zero anyway).

Finally we're doing Branch and Link instruction to the address where our function “wrapper” is located:

bl 0x80c8 <wrapper>

This instruction modifies PC and LR:

lr             0x8120 33056
pc             0x80c8 0x80c8 <wrapper>

LR is pointing to the next instruction after the Branch and Link in _start function and the PC points to the first instruction in wrapper() function. Stack in this example is not touched at this point.
On the prologue of the wrapper() function we see the same two instruction as before: push FP and LR to the stack and update FP register:

=> 0x000080c8 <+0>: push {r11, lr}
   0x000080cc <+4>: add r11, sp, #4

At this point we have registers as follows:

r11            0xbe9d28e4
sp             0xbe9d28e0
lr             0x8120
pc             0x80d0

And stack around SP:

If you get back to source code of function “wrapper”, you'll see it creates two local variables: integer “a” and the array of 24 integers. It also calls function “bar” which takes more than 4 arguments. In ARM, first 4 arguments are stored in registers before calling the function. If you need more arguments, they will be stored on the stack. All in all we need 24 words for the array + 1 word for the integer + 3 words for additional arguments that we want to pass to the next function. It gives us 112 bytes of memory that we want to use on the stack. This memory will be acquired by simple moving the Stack Pointer:

0x000080d0 <+8>: sub sp, sp, #120

Hurray. We've allocated memory. It's actually 120 bytes instead of 112 because of alignments required by processor.

Because FP was stored at the beginning of the function, compiler can refer to it while finding addresses on the stack. Our integer “a” should have value “4” and this is achieved with following instructions:

 0x000080d4 <+12>: mov r3, #4
 0x000080d8 <+16>: str r3, [r11, #-8]

Here's the stack after those instructions:

Because “allocating” memory for our buf[24] is just moving the Stack Pointer and because “deleting” local variables is also just moving Stack Pointer back, you should always initialize local variables. In our example, buf[24] gets a fresh, not used before stack so it's zeroed. In general case there will be leftovers from previous stack operations so the content of the uninitialized buf[24] should be concerned as garbage.

Now we finished with two local variables (although buf[24] is not used anywhere). Next, compiler needs to prepare arguments for calling the “bar” function:

0x000080dc <+20>: mov r3, #5
0x000080e0 <+24>: str r3, [sp]
0x000080e4 <+28>: mov r3, #6
0x000080e8 <+32>: str r3, [sp, #4]
0x000080ec <+36>: mov r3, #7
0x000080f0 <+40>: str r3, [sp, #8]
0x000080f4 <+44>: ldr r0, [r11, #-8]

Those instruction will save “5”, “6” and “7” on the stack, just before Stack Pointer:

Next step is to prepare arguments in registers r0-r3:

0x000080f4 <+44>: ldr r0, [r11, #-8]
0x000080f8 <+48>: mov r1, #2
0x000080fc <+52>: mov r2, #3
0x00008100 <+56>: mov r3, #4

Variable “a” is taken from the stack as expected (address is calculated in relation to FP). Other values are of course immediate in our simple example. To sum up: before issuing next Branch and Link instruction, compiler saved first 4 arguments in registers r0-r4 and put other arguments on the stack. It's time for the next frame:

0x00008104 <+60>: bl 0x8050 <bar>

Function “bar” is doing exactly the same thing: stores the frame pointer and link register on the stack, allocates some bytes by moving SP and prepare arguments in registers r0-r2 to call function “foo”. Lets go forward and assume we're returning from function “bar”. We'll get back to “foo” after that because it's slightly different.

Here's the ending of the function:

0x000080bc <+108>: mov r0, r3
0x000080c0 <+112>: sub sp, r11, #4
0x000080c4 <+116>: pop {r11, pc}

Return value is stored in r0. Then, Stack Pointer is simply moved back to the beginning of the stack frame with a help of the frame pointer. Finally, previous Frame Pointer is restored from the stack as well as Link Register is loaded into Program Counter. “pop” instruction will also increase SP accordingly to how many values are taken from the stack (in our example 2 words).

Regarding the “foo()”: compiler noticed that link register will not be touched douring call of the function, so the prologue is simplified:

Dump of assembler code for function foo:

   0x00008000 <+0>: push {r11}  ; (str r11, [sp, #-4]!)
=> 0x00008004 <+4>: add r11, sp, #0

It saves only frame pointer on the stack and updates it with current SP. At the exit following instructions are executed:

0x00008040 <+64>: mov r0, r3
0x00008044 <+68>: sub sp, r11, #0
0x00008048 <+72>: pop {r11}  ; (ldr r11, [sp], #4)
0x0000804c <+76>: bx lr

It stores return value in r0, moves SP back, restores frame pointer and issues Branch and Exchange instruction to the address pointed by Link Register. Branch and Exchange is a branch instruction with optional mode switch to Thumb. Lets see how the LR looks before this instruction:

lr             0x80b4 32948

The Branch and Exchange will switch to Thumb only if the less significant bit of the address is “1”. In our case 0x80b4 has “0” at last bit, so it will do just a normal ARM branch.
Here's how stack looks around SP before exiting from the “foo” function:

After the "0x00008044 <+68>: sub sp, r11, #0":

After the "0x00008048 <+72>: pop {r11}":

And finally we just branch back to the Link Registers and so we land one instruction after the original branch:

   0x000080b0 <+96>: bl 0x8000 <foo>
=> 0x000080b4 <+100>: str r0, [r11, #-12]  ← we continue here

If we would compile it with -fomit-frame-pointer, prologues will be little simplified but all addresses will be calculated in relation to SP. See example:

function wrapper with frame pointer:

000080c8 <wrapper>:
    80c8: e92d4800  push {fp, lr}
    80cc: e28db004  add fp, sp, #4
    80d0: e24dd078  sub sp, sp, #120 ; 0x78
    80d4: e3a03004  mov r3, #4
    80d8: e50b3008  str r3, [fp, #-8]
    80dc: e3a03005  mov r3, #5
    80e0: e58d3000  str r3, [sp]
    80e4: e3a03006  mov r3, #6
    80e8: e58d3004  str r3, [sp, #4]
    80ec: e3a03007  mov r3, #7
    80f0: e58d3008  str r3, [sp, #8]
    80f4: e51b0008  ldr r0, [fp, #-8]
    80f8: e3a01002  mov r1, #2
    80fc: e3a02003  mov r2, #3
    8100: e3a03004  mov r3, #4
    8104: ebffffd1  bl 8050 <bar>
    8108: e1a00000  nop               ; (mov r0, r0)
    810c: e24bd004  sub sp, fp, #4
    8110: e8bd8800  pop {fp, pc}

the same function without frame pointer:

000080b8 <wrapper>:
    80b8: e52de004  push {lr}  ; (str lr, [sp, #-4]!)
    80bc: e24dd07c  sub sp, sp, #124 ; 0x7c
    80c0: e3a03004  mov r3, #4
    80c4: e58d3074  str r3, [sp, #116] ; 0x74
    80c8: e3a03005  mov r3, #5
    80cc: e58d3000  str r3, [sp]
    80d0: e3a03006  mov r3, #6
    80d4: e58d3004  str r3, [sp, #4]
    80d8: e3a03007  mov r3, #7
    80dc: e58d3008  str r3, [sp, #8]
    80e0: e59d0074  ldr r0, [sp, #116] ; 0x74
    80e4: e3a01002  mov r1, #2
    80e8: e3a02003  mov r2, #3
    80ec: e3a03004  mov r3, #4
    80f0: ebffffd3  bl 8044 <bar>
    80f4: e1a00000  nop   ; (mov r0, r0)
    80f8: e28dd07c  add sp, sp, #124 ; 0x7c
    80fc: e49df004  pop {pc}  ; (ldr pc, [sp], #4)

To sum up: allocating memory on the stack means toggling back and forward the stack pointer and (optionally) the frame pointer. Stack grows downwards and “freeing memory” by moving the stack pointer does absolutely nothing with the underlying data (what makes it also a quick operation). We also observed how the arguments are passed to the functions and where the return value is stored.


Dynamic memory

Now, we can start allocating and accessing some dynamic memory. Because we're not using standard library for now, we need to handle '''system calls''' manually. We definitely need those system calls, since as a userspace application we don't have full access to the underlying hardware (RAM) and we need to ask OS for it (refer to ARM processor modes/rings).  Lets see how system calls are implemented on ARM. Example implementation of brk() system call looks as following:

0x400942dc <+0>: mov r12, r7
0x400942e0 <+4>: mov r7, #45 ; 0x2d   <--- store syscall number in r7
0x400942e4 <+8>: svc 0x00000000       <--- generate an exception
0x400942e8 <+12>:       mov r7, r12
0x400942ec <+16>: cmn r0, #4096 
0x400942f0 <+20>: bxls lr
0x400942f4 <+24>: rsb r0, r0, #0
0x400942f8 <+28>: b 0x400b1b40       <--- errno handling

Each system call have a specific number. Linux Kernel ABI for ARM specifies that we need to store  the system call number in register R7. In our example we're storing number “45” which is sys_brk().  All system calls numbers can be read here: kernel/arch/arm/kernel/calls.S. After storing the system call number, the actual transition to the Kernel space happens with usage of “SVC” instruction. It's a “Supervisor Call” - formerly this instruction was called “SWI” like “Software Interrupt” (only name has changed).  It generates a processor exception, so the CPSR is modified to enter supervisor mode and control flow is passed to the vector table and from there to vector_swi in kernel/arch/arm/kernel/entry-common.S. According to ARMv7-A specification, the vector_swi is a handler registered in exception vector + 0x08 offset. Every time a given exception is triggered, processor changes the control flow to the “vector table”. Base address of this table can be configured during initialization in SCTLR (System Control Register). In case of Android device I'm working on, the exception vector is at 0xFFFF0000. It can be configured to other address in Secure mode (TrustZone). You can read more about it in ARM-ARM  “B1.8.1 Exception vectors and the exception base address”.
Anyway, in our example we can see that in kernel/arch/arm/kernel/entry-armv.S there is a __vectors_start symbol which at offset 0x08 has a branch instruction to the vector_swi: "(ldr) pc, __vectors_start + 0x1000". So, after issuing “svc” instruction, processor executes that branch instruction and moves to vector_swi in kernel/arch/arm/kernel/entry-common.S. It does there couple more things related to maintenance of registers (like saving CPSR). Next, from vector_swi we branch to the specific sys_* handler:

ldrcc   pc, [r8, r7, lsl #2]
(in r8 there is our sys_call_table from calls.S and in r7 there is our system call number)

For “brk” system call  it means we'll execute the SYSCALL_DEFINE1(brk, unsigned long, brk) in kernel/mm/mmap.c .  Here actual kernel memory management happens. For now, we just assume it should increase heap area for our process. Quoting from brk() manual:

“brk()  and  sbrk()  change  the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment).  Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory.”

Our first goal is to check if it actually works.  Firstly, we need to call brk() with “zero” as an argument. It will give us current address of brk in our process (read again this blog if you don't know what program break is). After that, we can increment this address by some value and call brk() again. As a result, the heap area should be created for our process:

1 2 3 4 5 6 7 8 9 10 11 12

void main() { asm volatile ( "mov r0, #0\n" // first brk needs zero as an argument "mov r7, #45\n" // 45 is a brk syscall number "swi #0\n" // execute brk syscalli "mov r1, r0\n" // save return address in r1 "add r0, r1, #8192\n" // increase brk for 2 pages "swi #0\n" // increase heap (execute brk again, “45” is already in r7) }; while(1); // of course instead of loop we can use GDB to set a breakpoint }

This simple program will ask Kernel for 2 pages (8192 bytes) of memory. We can see now:

root@SGP621:/proc/4679 # cat maps 
00008000-00009000 r-xp 00008000 b3:1a 24441      /data/brk_test 
00fd0000-00fd2000 rwxp 00000000 00:00 0          [heap] 
b6f7a000-b6f7b000 r-xp 00000000 00:00 0          [sigpage] 
bee40000-bee61000 rwxp 00000000 00:00 0          [stack] 
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors] 

New area is created, called “heap”. Looking into more detailed view (in smaps):

00fd0000-00fd2000 rwxp 00000000 00:00 0          [heap] 
Size:                  8 kB 
Rss:                   0 kB 
Pss:                   0 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB 
Private_Dirty:         0 kB 
Referenced:            0 kB 
Anonymous:             0 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB 

We see in field “size” that Kernel created for us 8KB of virtual memory space. Because we're using memory over-committing, Kernel only reserved the memory for us, but did NOT allocate anything. For now, it only updated Kernel internal structures like mm_struct or vm_area_struct. We see, that “Rss” value is still zero. The actual memory allocation will happen when we will try to use the memory we've asked for. Let's try writing example data (number “255”) into both pages we've requested by brk():

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

void main() { asm volatile ( "mov r0, #0\n" // first brk needs null as an argument "mov r7, #45\n" // 45 is a brk syscall number "swi #0\n" // execute brk syscalli "mov r1, r0\n" // save return address in r1 "add r0, r1, #8192\n" // increase brk for 2 pages "swi #0\n" // increase heap (execute brk again) "mov r2, #255\n" // write "255" to tmp register "str r2, [r1]\n" // write "255" to memory to the beginning of the heap (page fault will happen) "str r2, [r1, #32]\n" // write "255" to memory to the 32 bytes from beginning (no page fault) "mov r3, #4096\n" // use r3 as a tmp register to calculate offset "str r2, [r1, r3]\n" // write "255" to the second page (page fault) }; while(1); }

The result is:

01b01000-01b03000 rwxp 00000000 00:00 0          [heap] 
Size:                  8 kB 
Rss:                   8 kB  <-- increased
Pss:                   8 kB  <-- increased
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB  
Private_Dirty:         8 kB  <-- increased
Referenced:            8 kB 
Anonymous:             8 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB

So, what happened? When for the first time we executed “store” instruction, the MMU in processor couldn't find any entry in its page table that corresponds to the virtual address we were referring to. In that case, the MMU throws the data_abort exception which is handled by kernel as minor page fault and results with starting Kernel memory management mechanism which allocates the actual memory (see kernel/arch/arm/mm/fault.c). We'll explain Kernel internals later. For now, we need to assume, that after allocating this memory, new entry in page table for our process is created and the “store” instruction is re-tried. Now, the entry is present, and the instruction succeeds. Because we're operating on page_size blocks, any other access inside this page will also succeed, but the another page fault will happen for access inside the second page we've requested. To see it better, you can use GDB and go instruction-by-instruction.

The conclusion from above example is that (assuming memory over-commit is set to “1”, which is true in most cases) Kernel will always give us virtual memory, but it doesn't mean that there is a physical resource available at all. We can get Out of Memory situation while referencing this memory.

In the same way you can check how stack area works and how global variables are handled. We'll now move to other way of getting dynamic memory from kernel: using mmap. We're inspecting brk() and mmap() because those are main system calls used by dlmalloc() adn jemalloc().

This is the moment in which you should read manual of mmap(). In short words, mmap() allows you to map a file into the virtual memory so the file can be accessed like it would be in the RAM. Of course, the big advantage of mmaping file (because of demand paging mechanism) is that not entire file is physically copied at once to the memory, but only when particular data is needed. It's also useful when you have many processes that read data from the same file. Kernel can share such mmaped file between all processes and hence save the RAM. The obvious example are shared libraries.
However, mmap() can be also used to just create (reserve) some virtual memory area without having actual file underneath. This is called anonymous mapping and it's heavily used by dlmalloc() and jemalloc(). So, the mmap can be used to create a memory area that programmer can use as dynamic allocated memory. The big advantage of mmap() over brk() is that you can unmap any mmaped space and re-use it. In case of brk() you can only decrease or increase the heap, so if you release some memory in the bottom of your brk()-created area, then you have an unused hole in you virtual memory area (memory fragmentation). You can't use it again with brk() unless you decrement the whole brk() to that point (discarding other memory). That way, the brk()-based heap is actually kind of stack. In dlmalloc() only small allocations are done using brk() call (which is in other hand quite fast). Everything above certain trigger is allocated with usage of mmap().

Declaration of mmap is following:

1	void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

We want to call it with those arguments:

1	addr = mmap(0, 8192, PROT_WRITE | PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, -1. 0);

It should return the virtual address from which we can use 2 pages (8192 bytes) of read/write private memory.

The system call number for mmap is 192. Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

void main() { asm volatile ( "mov r0, #0\n" // void *addr = 0 "mov r1, #8192\n" // size_t length = 2 pages "mov r2, #3\n" // int prot = PROT_WRITE | PROT_READ "mov r3, #34\n" // int flags = MAP_PRIVATE | MAP_ANONYMOUS "mov r4, #-1\n" // int fd = -1 "mov r5, #0\n" // off_t offset = 0 "push {r4, r5}\n" // push arguments onto stack "mov r7, #192\n" // 192 is a mmap2 syscall "swi #0\n" // call mmap2 "mov r2, #255\n" // write example value "255" to tmp register "str r2, [r0]\n" // write "255" to the mmpaped memory ); while(1); }

After building it and running through GDB, we can have a look at /proc//maps for the reference:

00008000-00009000 r-xp 00008000 b3:19 215        /data/mkmmap 
b6f64000-b6f65000 r-xp 00000000 00:00 0          [sigpage] 
bed62000-bed83000 rwxp 00000000 00:00 0          [stack] 
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors] 

Now. move instruction by instruction observing the /proc/<pid>/maps in other shell. Move by issuing “ni” command in GDB until swi instruction (remember to add to the GDB config “display/i $pc “).  Now, execute the swi and see the /proc<pid>maps output:

root@D5803:/proc/8186 # cat maps                                               
00008000-00009000 r-xp 00008000 b3:19 215        /data/mkmmap 
b6f62000-b6f64000 rwxp 00000000 00:00 0                         <-- new area
b6f64000-b6f65000 r-xp 00000000 00:00 0          [sigpage] 
bed62000-bed83000 rwxp 00000000 00:00 0          [stack] 
ffff0000-ffff1000 r-xp 00000000 00:00 0          [vectors]

New area appeared without any name. Lets see details in /proc/<pid>/smaps:

b6f62000-b6f64000 rwxp 00000000 00:00 0 
Size:                  8 kB 
Rss:                   0 kB 
Pss:                   0 kB 
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB 
Private_Dirty:         0 kB 
Referenced:            0 kB 
Anonymous:             0 kB 
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB 

It has 8kB size, so 2 pages as we requested. Note, that it's only virtual area reserved, there is 0kB of “referenced” memory. Lets see how many minor page faults our process has so far (10th entry in stat):

root@D5803:/proc/8186 # cat stat                                               
8186 (mkmmap) t 8183 8186 7923 34816 8186 4194304 >>63<< 0 0 0 0 0 0 0 20 0 1 0 85958 155648 2 4294967295 32768 32824 3201837312 3201837300 32812 0 0 268435456 0 3222961244 0 0 17 0 0 0 0 0 0 32768 32824 2453504

It's 63 page faults (so far, the number of page faults is related to loading the program itself for example by issuing execve() system call by the shell). Now, lets try to write sample value “255” to our newly created vm area by executing next two instructions (the mov and str).

After that we can see smaps:

6f62000-b6f64000 rwxp 00000000 00:00 0 
Size:                  8 kB 
Rss:                   4 kB   <-- updated
Pss:                   4 kB   <-- updated
Shared_Clean:          0 kB 
Shared_Dirty:          0 kB 
Private_Clean:         0 kB   
Private_Dirty:         4 kB   <-- updated
Referenced:            4 kB   <-- updated
Anonymous:             4 kB   <-- updated
AnonHugePages:         0 kB 
Swap:                  0 kB 
KernelPageSize:        4 kB 
MMUPageSize:           4 kB 
Locked:                0 kB

stat (10th entry = 68):

8186 (mkmmap) t 8183 8186 7923 34816 8186 4194304 >>68<< 0 0 0 0 0 0 0 20 0 1 0 85958 155648 2 4294967295 32768 32824 3201837312 32

Again (as in previous example about brk), when we issued “str” instruction (store in the memory), the processor asked MMU to find in its page table the physical address corresponding to our virtual address returned in r0 by mmap system call. MMU didn't find anything, so it generated an exception, Exception was handled as “minor page fault” which triggered actual memory allocation in the Kernel. The proper physical address was found and page table was updated. After that, the “str” instruction was repeated and now succeeded. Value “255” has been written to the RAM. Note, that we see 5 more minor page faults in the stat. Using GDB each instruction generates 2 minor page faults. We executed two instruction, but the “str” gave us 3 minor page faults. The additional one was related to our actual memory allocation.  In smaps we also see, that Rss and Pss fields were updated as well as Referenced and “Anonymous”. As we expected, now we have 4kB of new private, anonymous memory for our process. When we “touch” second page of our 8kB mmap area the same mechanism will be triggered.

Note, the '''major page fault''' would happen if we mmap actual file instead of anonymous mapping. In such case, Kernel will need to access the flash memory to copy page to the cache.

To sum up dynamic memory allocation or rather the process of requesting Kernel for dynamic memory: the main system calls that userspace application can use are brk() and mmap(), however there are number of other system calls related to memory management like madvise() or mprotect(). The smallest chunk of memory that OS can give to userspace is of '''PAGE_SIZE'''. When the memory overcommit is enabled, actual memory allocation will happen during accessing given address with usage of processor exceptions and page fault handling.