diff --git a/build/utils/BUILD b/build/utils/BUILD
new file mode 100644
index 0000000..0a3454b
--- /dev/null
+++ b/build/utils/BUILD
@@ -0,0 +1,86 @@
+# TODO(leo): I have not been able to figure out a clever way of separating this
+# into multiple rules, particularly musl, which hardcodes sandbox paths into its
+# toolchain such that a different rule cannot consume it.
+#
+# For now, using a single massive genrule is the least annoying way to do this.
+# As soon as we build more than just mkfs.xfs, we should re-visit this.
+#
+# Some possibilities:
+#
+#  - Build the musl toolchain in the build container and use native rules
+#    for headers_install and util_linux (they should, in theory, generate
+#    well-defined artifacts that we can use in the build).
+#
+#    This would use Bazel's toolchain definition mechanism to consume the
+#    external toolchain, and would be compatible with the native C rules.
+#
+#    Maybe we can even build the external toolchain inside Bazel somehow?
+#
+#  - Write a custom rule that handles the toolchain.
+#
+#  - Converting *everything* to native rules is probably not an option due
+#    to how complex the third party build systems we touch are.
+
+genrule(
+    name = "utils",
+    srcs = [
+        "@xfsprogs_dev//:all",
+        "@musl//:all",
+        "@util_linux//:all",
+        "@linux_kernel//:all",
+    ],
+    outs = [
+        "mkfs.xfs",
+    ],
+    cmd = """
+    MUSL=$$PWD/$(RULEDIR)/musl_prefix
+
+    echo "Compiling and installing musl..."
+    (
+        cd external/musl
+        ./configure --prefix=$$MUSL
+        make -j 8 install
+    ) > /dev/null
+
+    echo "Installing Linux kernel headers..."
+    (
+        cd external/linux_kernel
+        make headers_install ARCH=x86_64 INSTALL_HDR_PATH=$$MUSL
+    ) > /dev/null
+
+    echo "Compiling util_linux..."
+    (
+        cd external/util_linux
+        ./autogen.sh
+        ./configure \
+        CC="$$MUSL/bin/musl-gcc" \
+        --without-systemd \
+        --without-udev \
+        --without-btrfs \
+        --disable-pylibmount \
+        --without-tinfo \
+        --prefix=$$MUSL \
+        --disable-makeinstall-chown \
+        --disable-makeinstall-setuid \
+        --with-bashcompletiondir=$$MUSL/usr/share/bash-completion
+        make -j8 libuuid.la libblkid.la
+        echo "Installing util_linux..."
+        cp -v .libs/* $$MUSL/lib/
+        mkdir -p $$MUSL/include/{uuid,blkid}
+        cp libuuid/src/uuid.h $$MUSL/include/uuid/
+        cp libblkid/src/blkid.h $$MUSL/include/blkid/
+    ) > /dev/null
+
+    echo "Compiling mkfs.xfs..."
+    (
+        cd external/xfsprogs_dev
+        make configure
+        ./configure CC="$$MUSL/bin/musl-gcc" CFLAGS="-static" --prefix=$$MUSL
+        echo COMPILERING
+        make mkfs
+    ) > /dev/null
+
+    cp external/xfsprogs_dev/mkfs/mkfs.xfs $(RULEDIR)
+    """,
+    visibility = ["//visibility:public"],
+)
diff --git a/build/utils/xfsprogs_dev/0001-Fixes-for-static-compilation.patch b/build/utils/xfsprogs_dev/0001-Fixes-for-static-compilation.patch
new file mode 100644
index 0000000..14dd4cd
--- /dev/null
+++ b/build/utils/xfsprogs_dev/0001-Fixes-for-static-compilation.patch
@@ -0,0 +1,64 @@
+Copyright 2020 The Monogon Project Authors.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+  http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+
+
+From 780a94ddc5c50bded264bfc0dbfffdb4182cdc51 Mon Sep 17 00:00:00 2001
+From: Lorenz Brun <lorenz@nexantic.com>
+Date: Mon, 9 Sep 2019 15:56:42 +0200
+Subject: [PATCH] Fixes for static compilation
+
+---
+ include/xfs.h | 6 +++---
+ mkfs/Makefile | 2 +-
+ 2 files changed, 4 insertions(+), 4 deletions(-)
+
+diff --git a/include/xfs.h b/include/xfs.h
+index f2f675df..73687a16 100644
+--- a/include/xfs.h
++++ b/include/xfs.h
+@@ -6,7 +6,7 @@
+ #define __XFS_H__
+ 
+ #if defined(__linux__)
+-#include <xfs/linux.h>
++#include "linux.h"
+ #else
+ # error unknown platform... have fun porting!
+ #endif
+@@ -34,7 +34,7 @@ extern int xfs_assert_largefile[sizeof(off_t)-8];
+ #define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
+ #endif
+ 
+-#include <xfs/xfs_types.h>
+-#include <xfs/xfs_fs.h>
++#include "xfs_types.h"
++#include "xfs_fs.h"
+ 
+ #endif	/* __XFS_H__ */
+diff --git a/mkfs/Makefile b/mkfs/Makefile
+index 31482b08..57fb355d 100644
+--- a/mkfs/Makefile
++++ b/mkfs/Makefile
+@@ -13,7 +13,7 @@ CFILES = proto.c xfs_mkfs.c
+ LLDLIBS += $(LIBXFS) $(LIBXCMD) $(LIBFROG) $(LIBRT) $(LIBPTHREAD) $(LIBBLKID) \
+ 	$(LIBUUID)
+ LTDEPENDENCIES += $(LIBXFS) $(LIBXCMD) $(LIBFROG)
+-LLDFLAGS = -static-libtool-libs
++LLDFLAGS = -all-static
+ 
+ default: depend $(LTCOMMAND)
+ 
+-- 
+2.20.1
+
diff --git a/build/utils/xfsprogs_dev/BUILD b/build/utils/xfsprogs_dev/BUILD
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/build/utils/xfsprogs_dev/BUILD