macOS: queue for munmap operations

From: Koji Nakamaru <[email protected]>

Executing many mmap/munmap calls alternately can cause a huge load on macOS. In order to reduce it, we should temporarily store munmap operations in a queue and process them all at once when the queue is filled. When the program terminates, we can discard any remaining munmap operations as corresponding mmaped regions are automatically reclaimed.

Add a queue for munmap operations to perform them all at once.

Here are some example timings. On the Linux kernel repository that requires about 1700 mmap/munmap calls:

  time git ls-tree -r -l --full-tree 211ddde > /dev/null

Before:

        real    0m2.083s
        user    0m0.201s
        sys     0m1.873s

After:

        real    0m0.243s
        user    0m0.179s
        sys     0m0.052s

On a private repository that requires about 943000 mmap/munmap calls:

  time git ls-tree -r -l --full-tree xxxxxxx > /dev/null

Before:

        real    27m15.138s
        user    0m5.084s
        sys     27m9.636s

After:

        real    0m24.209s
        user    0m3.055s
        sys     0m21.123s

Signed-off-by Koji Nakamaru <[email protected]>

---
macOS: queue for munmap operations

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1993%2FKojiNakamaru%2Ffeature%2Fosx-queued-munmap-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1993/KojiNakamaru/feature/osx-queued-munmap-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1993

 Makefile                            |  1 +
 compat/osxmmap.c                    | 49 +++++++++++++++++++++++++++++
 compat/posix.h                      |  7 +++++
 contrib/buildsystems/CMakeLists.txt |  4 +++
 meson.build                         |  2 ++
 5 files changed, 63 insertions(+)
 create mode 100644 compat/osxmmap.c

Makefile +1 -0

index f79c905bdc..058bc83753 100644
@@ -1654,6 +1654,7 @@ ifeq ($(uname_S),Darwin)
 		COMPAT_CFLAGS += -DAPPLE_COMMON_CRYPTO
         endif
 	PTHREAD_LIBS =
+	COMPAT_OBJS += compat/osxmmap.o
 endif
 
 ifdef NO_LIBGEN_H

compat/osxmmap.c new file +2 -0

new file mode 100644
index 0000000000..5f9cf633ca
@@ -0,0 +1,49 @@
+#include <pthread.h>
+#include "../git-compat-util.h"

compat/osxmmap.c new file +25 -0

+	if (start != NULL || flags != MAP_PRIVATE || prot != PROT_READ)
+		die("invalid usage of mmap");
+	return mmap(start, length, prot, flags, fd, offset);
+}
+
+int git_munmap(void *start, size_t length)
+{
+	static pthread_mutex_t mutex;
+	static struct munmap_queue *queue;
+	static int count;
+	int i;
+
+	pthread_mutex_lock(&mutex);
+	if (!queue)
+		queue = xmalloc(COUNT_MAX * sizeof(struct munmap_queue));
+	queue[count].start = start;
+	queue[count].length = length;
+	if (++count == COUNT_MAX) {
+		for (i = 0; i < COUNT_MAX; i++)
+			munmap(queue[i].start, queue[i].length);
+		count = 0;
+	}
+	pthread_mutex_unlock(&mutex);
+	return 0;
+}

compat/posix.h +0 -0

index 067a00f33b..3fa1218289 100644

compat/posix.h +6 -0

+#define mmap git_mmap
+#define munmap git_munmap
+void *git_mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
+int git_munmap(void *start, size_t length);
+#endif
+
 #endif /* NO_MMAP || USE_WIN32_MMAP */
 
 #ifndef MAP_FAILED

contrib/buildsystems/CMakeLists.txt +4 -0

index edb0fc04ad..5c08f2fe5c 100644
@@ -271,6 +271,10 @@ if(CMAKE_SYSTEM_NAME STREQUAL "Windows")
 		compat/strdup.c)
 	set(NO_UNIX_SOCKETS 1)
 
+elseif(CMAKE_SYSTEM_NAME STREQUAL "Darwin")
+	list(APPEND compat_SOURCES
+		compat/osxmmap.c)
+
 elseif(CMAKE_SYSTEM_NAME STREQUAL "Linux")
 	add_compile_definitions(PROCFS_EXECUTABLE_PATH="/proc/self/exe" HAVE_DEV_TTY )
 	list(APPEND compat_SOURCES unix-socket.c unix-stream-server.c compat/linux/procinfo.c)

meson.build +2 -0

index cee9424475..b9b6e731b1 100644
@@ -1275,6 +1275,8 @@ elif host_machine.system() == 'windows'
   else
     libgit_sources += 'compat/mingw.c'
   endif
+elif host_machine.system() == 'darwin'
+  libgit_sources += 'compat/osxmmap.c'
 endif
 
 if host_machine.system() == 'linux'

base-commit: 4253630c6f07a4bdcc9aa62a50e26a4d466219d1

Signature · 1 line

gitgitgadget

Some comments inline, all up to improvements

Quoted 8 lines · Koji Nakamaru via GitGitGadget

From: Koji Nakamaru <[email protected]>

Executing many mmap/munmap calls alternately can cause a huge load on macOS. In order to reduce it, we should temporarily store munmap operations in a queue and process them all at once when the queue is filled. When the program terminates, we can discard any remaining munmap operations as corresponding mmaped regions are automatically reclaimed.

Quoted 2 lines

Add a queue for munmap operations to perform them all at once.

Suggestions for rewording:
In order to reduce the peak load store all munmap operations in a queue. Process them all at once (and more efficient) when the queue is filled. The queue may be ignored when the git process terminates. The operating system will do all munmap() when the process exits.

Quoted 71 lines

Here are some example timings. On the Linux kernel repository that requires about 1700 mmap/munmap calls:

  time git ls-tree -r -l --full-tree 211ddde > /dev/null

Before:

        real    0m2.083s
        user    0m0.201s
        sys     0m1.873s

After:

        real    0m0.243s
        user    0m0.179s
        sys     0m0.052s

On a private repository that requires about 943000 mmap/munmap calls:

  time git ls-tree -r -l --full-tree xxxxxxx > /dev/null

Before:

        real    27m15.138s
        user    0m5.084s
        sys     27m9.636s

After:

        real    0m24.209s
        user    0m3.055s
        sys     0m21.123s

Signed-off-by Koji Nakamaru <[email protected]>

---
macOS: queue for munmap operations

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1993%2FKojiNakamaru%2Ffeature%2Fosx-queued-munmap-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1993/KojiNakamaru/feature/osx-queued-munmap-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1993

 Makefile                            |  1 +
 compat/osxmmap.c                    | 49 +++++++++++++++++++++++++++++
 compat/posix.h                      |  7 +++++
 contrib/buildsystems/CMakeLists.txt |  4 +++
 meson.build                         |  2 ++
 5 files changed, 63 insertions(+)
 create mode 100644 compat/osxmmap.c

Makefile +1 -0

index f79c905bdc..058bc83753 100644
@@ -1654,6 +1654,7 @@ ifeq ($(uname_S),Darwin)
              COMPAT_CFLAGS += -DAPPLE_COMMON_CRYPTO
         endif
      PTHREAD_LIBS =
+     COMPAT_OBJS += compat/osxmmap.o
 endif
 
 ifdef NO_LIBGEN_H

compat/osxmmap.c new file +8 -0

new file mode 100644
index 0000000000..5f9cf633ca
@@ -0,0 +1,49 @@
+#include <pthread.h>
+#include "../git-compat-util.h"
+/* We need original mmap/munmap here. */
+#undef mmap
+#undef munmap
+
+/*
+ * OSX doesn't have any specific setting like Linux's vm.max_map_count,

compat/osxmmap.c line 12

Quoted 4 lines

compat/osxmmap.c new file +4 -0

+ * so COUNT_MAX can be any large number. We here set it to the default
+ * value of Linux's vm.max_map_count.
+ */
+#define COUNT_MAX (65530)

Why the parantheses ?
And would a less generic name be better, like
MAX_UNMAP_COUNT

Quoted 7 lines

compat/osxmmap.c new file +7 -0

+
+struct munmap_queue {
+     void *start;
+     size_t length;
+};
+
+void *git_mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset)

compat/osxmmap.c line 24

Quoted 5 lines

compat/osxmmap.c new file +5 -0

+{
+     /*
+      * We can simply discard munmap operations in the queue by
+      * restricting mmap arguments.
+      */

Should I read this as
The munmap queue is only ment to defere read-only mappings. And that is what Git does at the moment.

Quoted 31 lines

compat/osxmmap.c new file +25 -0

+     if (start != NULL || flags != MAP_PRIVATE || prot != PROT_READ)
+             die("invalid usage of mmap");
+     return mmap(start, length, prot, flags, fd, offset);
+}
+
+int git_munmap(void *start, size_t length)
+{
+     static pthread_mutex_t mutex;
+     static struct munmap_queue *queue;
+     static int count;
+     int i;
+
+     pthread_mutex_lock(&mutex);
+     if (!queue)
+             queue = xmalloc(COUNT_MAX * sizeof(struct munmap_queue));
+     queue[count].start = start;
+     queue[count].length = length;
+     if (++count == COUNT_MAX) {
+             for (i = 0; i < COUNT_MAX; i++)
+                     munmap(queue[i].start, queue[i].length);
+             count = 0;
+     }
+     pthread_mutex_unlock(&mutex);
+     return 0;
+}

compat/posix.h +0 -0

index 067a00f33b..3fa1218289 100644
@@ -278,6 +278,13 @@ int git_munmap(void *start, size_t length);
 

compat/posix.h int git_munmap(void *start, size_t length); · line 281

Quoted 3 lines

compat/posix.h +1 -0

 #include <sys/mman.h>
 
+#if defined(__APPLE__)

I think it would be better to have a global Makefile knob here. Which
a) allows to take out this patch once the MacOs kernel is improved
b) allows to hook in this code for other OS
Something like DEFER_MUNMAPS - better suggestions welcome

Quoted 1 line

[snip]

From: Koji Nakamaru <[email protected]>

Executing many mmap/munmap calls alternately can cause a huge load on macOS. In order to reduce it, we should temporarily store munmap operations in a queue and process them all at once when the queue is filled. When the program terminates, we can discard any remaining munmap operations as corresponding mmaped regions are automatically reclaimed.

Add a queue for munmap operations to perform them all at once.

Here are some example timings. On the Linux kernel repository that requires about 1700 mmap/munmap calls:

  time git ls-tree -r -l --full-tree 211ddde > /dev/null

On a private repository that requires about 943000 mmap/munmap calls:

  time git ls-tree -r -l --full-tree xxxxxxx > /dev/null

compat/osxmmap.c new file +10 -0

+int git_munmap(void *start, size_t length)
+{
+	static pthread_mutex_t mutex;
+	static struct munmap_queue *queue;
+	static int count;
+	int i;
+
+	pthread_mutex_lock(&mutex);
+	if (!queue)
+		queue = xmalloc(COUNT_MAX * sizeof(struct munmap_queue));

Quoted 8 lines · Koji Nakamaru via GitGitGadget

From: Koji Nakamaru <[email protected]>

Executing many mmap/munmap calls alternately can cause a huge load on macOS. In order to reduce it, we should temporarily store munmap operations in a queue and process them all at once when the queue is filled. When the program terminates, we can discard any remaining munmap operations as corresponding mmaped regions are automatically reclaimed.

Quoted 6 lines

Add a queue for munmap operations to perform them all at once.

Here are some example timings. On the Linux kernel repository that requires about 1700 mmap/munmap calls:

  time git ls-tree -r -l --full-tree 211ddde > /dev/null

Why is it doing so many mmap calls? Do you have a ton of loose objects? We have to mmap loose objects individually (because they're all in separate files), but each pack only gets a single map (well, there's a window parameter, but it's 1GB on 64-bit systems, so you should get a handful of maps at most).

If you run "git gc", how does the resulting ls-tree perform? I have only 27 mmap() calls on my system.

I know that running "git gc" is relatively expensive, but it is also bringing other optimizations (like the fact that we don't have to open() and map each of those files in the first place!).

Quoted 3 lines

On a private repository that requires about 943000 mmap/munmap calls:

  time git ls-tree -r -l --full-tree xxxxxxx > /dev/null

Ditto here. I'd be curious how well packed the repo is, and how it does after a repack. If it has a very large packfile, you might also try:

git config core.packedGitWindowSize 4G

or similar (though for just an ls-tree, we should only be looking at tree objects, which in general I'd expect to be in a confined area of the packfile; so the 1GB window is probably plenty).

Quoted 10 lines

compat/osxmmap.c new file +10 -0

+int git_munmap(void *start, size_t length)
+{
+     static pthread_mutex_t mutex;
+     static struct munmap_queue *queue;
+     static int count;
+     int i;
+
+     pthread_mutex_lock(&mutex);
+     if (!queue)
+             queue = xmalloc(COUNT_MAX * sizeof(struct munmap_queue));

compat/osxmmap.c line 49

Quoted 10 lines

compat/osxmmap.c new file +10 -0

+     queue[count].start = start;
+     queue[count].length = length;
+     if (++count == COUNT_MAX) {
+             for (i = 0; i < COUNT_MAX; i++)
+                     munmap(queue[i].start, queue[i].length);
+             count = 0;
+     }
+     pthread_mutex_unlock(&mutex);
+     return 0;
+}

Does batching those unmaps actually make them faster? Or is it just that the commands you showed did not fill the queue, so we essentially just leaked all of those maps until the program exited?

If the latter, then I'd wonder:

1. Does this increase memory pressure, since the OS has no idea we're not actually interested in those maps anymore? Some of them can be quite large, if the command is looking at blobs.

2. How does it perform on a command that actually fills the queue? I guess something like "git log --raw" might do it (though if my guesses above are right, you'd need on the order of 64,000 loose trees).

Quoted 8 lines

Ditto here. I'd be curious how well packed the repo is, and how it does after a repack. If it has a very large packfile, you might also try:

git config core.packedGitWindowSize 4G

or similar (though for just an ls-tree, we should only be looking at tree objects, which in general I'd expect to be in a confined area of the packfile; so the 1GB window is probably plenty).

Following your suggestion, I investigated the number of mmap calls in other environments and found much smaller counts. I tracked how xmmap_gently() was called in packfile.c and found settings->packed_git_window_size was different between environments. My ~/.gitconfig defined "packedGitLimit = 128m" and this caused many calls.

In my extreme cases, this batching makes them faster. Queue flushing has occurred several times for the private repository case and not occurred for the Linux kernel case. Though I haven't investigated in detail, memory pressure doesn't seem to be critical (and it could also be possible to adopt smarter thresholds).