Featured post

Linux Internals: How /proc/self/mem writes to unwritable memory

2 Replies
: _Deep Dive 🔍, C, Favorite, Linux Kernel

Introduction

An obscure quirk of the /proc/*/mem pseudofile is its “punch through” semantics. Writes performed through this file will succeed even if the destination virtual memory is marked unwritable. In fact, this behavior is intentional and actively used by projects such as the Julia JIT compiler and rr debugger.

This behavior raises some questions: Is privileged code subject to virtual memory permissions? In general, to what degree can the hardware inhibit kernel memory access?

By exploring these questions1, this article will shed light on the nuanced relationship between an operating system and the hardware it runs on. We’ll examine the constraints the CPU can impose on the kernel, and how the kernel can bypass these constraints.

Continue reading →
Featured post

Double fetches, scheduling algorithms, and onion rings

3 Replies
: _Essay 📝, Favorite, Life

Most people thought I was crazy for doing this, but I spent the last few months of my gap year working as a short order cook at a family-owned fast-food restaurant. (More on this here.) I’m a programmer by trade, so I enjoyed thinking about the restaurant’s systems from a programmer’s point of view. Here’s some thoughts about two such systems.

Continue reading →
Featured post

What they don’t tell you about demand paging in school

3 Replies
: _Deep Dive 🔍, C++, Favorite, Linux, Linux Kernel

This post details my adventures with the Linux virtual memory subsystem, and my discovery of a creative way to taunt the OOM (out of memory) killer by accumulating memory in the kernel, rather than in userspace.

Keep reading and you’ll learn:

  • Internal details of the Linux kernel’s demand paging implementation
  • How to exploit virtual memory to implement highly efficient sparse data structures
  • What page tables are and how to calculate the memory overhead incurred by them
  • A cute way to get killed by the OOM killer while appearing to consume very little memory (great for parties)

Note: Victor Michel wrote a great follow up to this post here.

Continue reading →
Featured post

How setjmp and longjmp work (2016)

2 Replies
: _Deep Dive 🔍, Assembly, C, Favorite, Linux

Pretty recently I learned about setjmp() and longjmp(). They’re a neat pair of libc functions which allow you to save your program’s current execution context and resume it at an arbitrary point in the future (with some caveats2). If you’re wondering why this is particularly useful, to quote the manpage, one of their main use cases is “…for dealing with errors and interrupts encountered in a low-level subroutine of a program.” These functions can be used for more sophisticated error handling than simple error code return values.

I was curious how these functions worked, so I decided to take a look at musl libc’s implementation for x86. First, I’ll explain their interfaces and show an example usage program. Next, since this post isn’t aimed at the assembly wizard, I’ll cover some basics of x86 and Linux calling convention to provide some required background knowledge. Lastly, I’ll walk through the source, line by line.

Continue reading →

How to do custom commands/targets in CMake

Leave a reply
: _Tech 💻, CMake

To run custom build stages in CMake, you’ll often want what I call a “custom command/target pair”:

set(CLEAN_FS_IMG ${CMAKE_CURRENT_BINARY_DIR}/clean-fs.img)
add_custom_target(CleanFsImage DEPENDS ${CLEAN_FS_IMG})
add_custom_command(
    OUTPUT ${CLEAN_FS_IMG}
    COMMAND ${CMAKE_CURRENT_BINARY_DIR}/fsformat ${CLEAN_FS_IMG} 1024 ${FS_IMG_FILES}
    WORKING_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR}
    DEPENDS fsformat ${FS_IMG_FILES}
    VERBATIM
)

This is an example from my CMake-rewrite of the JOS OS build system. It generates a filesystem image, using a custom host tool (fsformat). The fs image includes a number of files generated by the build process. If any of those files changes, we want to rebuild the fs image.

At the core, we want to have a CMake target, just like an executable or library, that runs an arbitrary command line instead of a compiler.

Surprisingly, we need this “command/target pair” pattern to accomplish this.

add_custom_target() alone is not correct. This target is always out of date. If we put the command there, we will regenerate the fs every build, even if nothing has changed. This makes custom targets only suitable for helper commands that must always run (e.g. perhaps a helper target to run QEMU)

add_custom_command() does implement efficient rebuilding, only when an input has changed, but is also not sufficient alone, because it does not produce a named target.

This is admittedly a matter of personal taste — I prefer having named targets available because it allows manually trigger just this target in a build command. This would not be otherwise possible with a custom command.

If you don’t have this requirement, just a custom command could be fine, since you can depend on the output file path elsewhere in your build.

The combination of both produces what I want:

  • A named target that can be independently triggered with a build command
  • A build stage that runs an arbitrary command that only rebuilds when necessary

In other words, what this pair states is:

  • Build CleanFsImage target always
  • When building it, ensure ${CLEAN_FS_IMG} is created/up to date by running whatever operation necessary (i.e. the custom command)
  • Then it’s up to the custom command to decide to run the command or not, based on if it’s necessary

A gotcha

One gotcha to be aware of is with chaining these command/target pairs.

set(FS_IMG ${CMAKE_CURRENT_BINARY_DIR}/fs.img)
add_custom_target(FsImage ALL DEPENDS ${FS_IMG})
add_custom_command(
    OUTPUT ${FS_IMG}
    COMMAND cp ${CLEAN_FS_IMG} ${FS_IMG} 
    # We cannot depend on CleanFsImage target here, because custom targets don't create
    # a rebuild dependency (only native targets do).
    DEPENDS ${CLEAN_FS_IMG}
    VERBATIM
)

In my build, I also have a FsImage target that just copies the clean one. This is one mounted by the OS, and might be mutated.

This custom command cannot depend on the CleanFsImage target, but rather must depend on the ${CLEAN_FS_IMG} path directly. That’s because custom targets don’t create a rebuild dependency (unlike native targets), just a build ordering.

In practice, the FsImage wasn’t being regenerated when the CleanFsImage was. To properly create a rebuild dependency, you must depend on the command target’s output path.

Pure GNU Make is (unfortunately) not enough

Leave a reply
: _Tech 💻, C, C++, CMake

I’d love to simply use GNU Make for my C/C++ projects because it’s so simple to get started with. Unfortunately it’s lacking a few essential qualify of life features:

  • Out of tree builds
  • Automatic header dependency detection
  • Recompile on CFLAGS change
  • First class build targets

Out of tree builds

If you want your build to happen in an isolated build directory (as opposed to creating object files in your source tree), you need to implement this yourself.

It involves a lot of juggling paths. Not fun!

Automatic header dependency detection

In C/C++, when a header file changes, you must recompile all translation units (i.e. object files, roughly) that depend on (i.e. include) that header. If you don’t, the object file will become stale and none of your changes to constants, defines, or struct definitions (for example) will be picked up.

In Make rules, you typically express dependencies between source files, and object files, e.g:

%.o: %.c
  # run compiler command here

This will recompile the object file when the source file changes, but won’t recompile when any headers included by that source file change. So it’s not good enough out of the box.

To fix this, you need to manually implement this by:

  1. Passing the proper flags to the compiler to cause it to emit header dependency information. (Something like -MMD. I don’t know them exactly because that’s my whole point =)
  2. Instructing the build to include that generate dependency info (Something like
    -include $(OBJECTS:.o=.d)    )

The generated dependency info looks like this:

pmap.c.obj: \
 kern/pmap.c \
 inc/x86.h \
 inc/types.h \
 inc/mmu.h \
 inc/error.h \
 inc/string.h \

Recompile on CFLAGS change

In addition to recompiling if headers change, you also want to recompile if any of your compiler, linker, or other dev tool flags change.

Make doesn’t provide this out of the box, you’ll also have to implement this yourself.

This is somewhat nontrivial. For an example, check out how the JOS OS (from MIT 6.828 (2018)) does it: https://github.com/offlinemark/jos/blob/1d95b3e576dd5f84b739fa3df773ae569fa2f018/kern/Makefrag#L48

First class build targets

In general, it’s nice to have build targets as a first class concept. They express source files compiled by the module, and include paths to reach headers. Targets can depend on each other and seamlessly access the headers of another target (the build system makes sure all -I flags are passed correctly).

This is also something you’d have to implement yourself, and there are probably limitations to how well your can do it in pure Make.

Make definitely has it’s place for certain tasks (easily execute commonly used command lines), but I find it hard to justify using it for anything non-trivially sized compared to more modern alternatives like CMake, Meson, Bazel, etc.

That said, large projects like Linux use it, so somehow they must make it work!

Show and tell: Suicide C Compiler

Leave a reply
: _Tech 💻

https://github.com/offlinemark/suicide

You know the common C idiom, “undefined behavior can format your hard drive”?

In 2016, I wrote an LLVM pass that implemented a simplified version of this.

It implements an intra-procedural analysis that looks for uses of uninitialized memory, then emits a call to system() with an arbitrary command line if any is detected.

Here’s roughly how the analysis works:

  • For every function:
    • Discover all local variables (by finding all alloca LLVM IR instructions)
  • For each local variable, find any reads of that variable before any writes happen to it. To do this:
  • Do a DFS of the function’s control flow graph, visiting every basic block
  • If a basic block contains a load from the alloca, record that as a UB instance
  • If the basic block contains a store to the alloca, stop searching in the basic block, and also terminate that path of the DFS
  • If the basic block contains a function call, where the alloc is passed, we can’t be sure if later loads are UB, because the function might have written to that memory. (We don’t know, because this is just an intra-procedural analysis). Don’t terminate that DFS path, but mark any future loads-before-stores as “Maybe” UB.

That’s it. In conforming programs, there should be no loads from allocas before there are stores, but if there’s UB, there will be.

Then for every UB load, emit a call to system() at that point.

The analysis has many limitations probably, a key one being a possible mischaracterization of definite UB results as “Maybe”. This is because each basic block is only visited once. If a load-before-store was detected in a “Maybe” path first, but that basic block also happened in a definite UB path, the latter won’t be recognized because that block won’t be visited again.

Overall, a fun project and nice exercise to try out LLVM.

#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"

#include <stack>
#include <unordered_set>

using namespace llvm;

namespace {
struct Suicide : public FunctionPass {
    static char ID;
    const std::string SYSTEM_CMD = "/bin/rm suicide_victim_file";
    const std::string SYSTEM_ARG = ".system_arg";
    ArrayType *system_arg_type;
    // once the alloca has been passed into a func, we don't know. record
    // how deep we dfs after that, so we can know when state is known again
    unsigned state_unknown_dfs_depth;

    Suicide() : FunctionPass(ID) {
    }
    bool runOnFunction(Function &F) override;

    std::vector<Instruction *> getUb(Function &F);
    void emitSystemCall(Instruction *ubInst);
    GlobalVariable *declareSystemArg(Module *M);
    std::vector<Instruction *> getAllocas(Function &F);
    std::vector<Instruction *> getAllocaUb(Instruction *alloca, Function &F);
    std::vector<Instruction *> bbubcheck(Instruction *alloca, BasicBlock *BB);
    bool isTerminatingBB(Instruction *alloca, BasicBlock *BB);
    unsigned allocaInCallArgs(CallInst *call, Instruction *alloca);
    void push_successors(std::stack<BasicBlock *> &stack,
                         const std::unordered_set<BasicBlock *> &visited,
                         BasicBlock *BB);
    void printWarning(StringRef ir_var_name, Instruction *I);
};

void Suicide::push_successors(std::stack<BasicBlock *> &stack,
                             const std::unordered_set<BasicBlock *> &visited,
                             BasicBlock *BB) {
    for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; I++) {
        if (!visited.count(*I)) {
            stack.push(*I);
            if (state_unknown_dfs_depth) {
                state_unknown_dfs_depth++;
            }
        }
    }
}

template <typename T> void vec_append(std::vector<T> &a, std::vector<T> &b) {
    a.insert(a.end(), b.begin(), b.end());
}

bool Suicide::runOnFunction(Function &F) {
    Module *M = F.getParent();

    std::vector<Instruction *> ubinsts = getUb(F);
    if (ubinsts.size() == 0) {
        return false;
    }

    if (!M->getGlobalVariable(SYSTEM_ARG, true)) {
        declareSystemArg(M);
    }

    for (const auto &inst : ubinsts) {
        emitSystemCall(inst);
    }

    return true;
}

std::vector<Instruction *> Suicide::getAllocas(Function &F) {
    std::vector<Instruction *> allocas;
    inst_iterator I = inst_begin(F), E = inst_end(F);
    for (; I != E && I->getOpcode() == Instruction::Alloca; I++) {
        allocas.push_back(&*I);
    }
    return allocas;
}

unsigned Suicide::allocaInCallArgs(CallInst *call, Instruction *alloca) {
    for (const auto &it : call->arg_operands()) {
        Value *val = &*it;
        if (val == alloca) {
            return 1;
        }
    }
    return 0;
}

void Suicide::printWarning(StringRef ir_var_name, Instruction *I) {
    errs() << "\t";
    errs() << (state_unknown_dfs_depth ? "[?] UNSURE" : "[!]   SURE");
    errs() << ": Uninitialized read of `" << ir_var_name << "` ; " << *I
           << "\n";
}

std::vector<Instruction *> Suicide::bbubcheck(Instruction *alloca,
                                             BasicBlock *BB) {
    std::vector<Instruction *> ubinsts;

    for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
        switch (I->getOpcode()) {
        case Instruction::Load: {
            LoadInst *load = cast<LoadInst>(&*I);
            Value *op = load->getPointerOperand();
            if (op == alloca) {
                printWarning(op->getName(), &*I);
                ubinsts.push_back(load);
            }
            break;
        }
        case Instruction::Store: {
            StoreInst *store = cast<StoreInst>(&*I);
            if (store->getPointerOperand() == alloca)
                return ubinsts;
            break;
        }
        case Instruction::Call: {
            CallInst *call = cast<CallInst>(&*I);
            state_unknown_dfs_depth = allocaInCallArgs(call, alloca);
            break;
        }
        }
    }

    return ubinsts;
}

bool Suicide::isTerminatingBB(Instruction *alloca, BasicBlock *BB) {
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; I++) {
        switch (I->getOpcode()) {
        case Instruction::Store: {
            StoreInst *store = cast<StoreInst>(&*I);
            if (store->getPointerOperand() == alloca)
                return true;
            break;
        }
        }
    }
    return false;
}

std::vector<Instruction *> Suicide::getAllocaUb(Instruction *alloca,
                                               Function &F) {
    std::vector<Instruction *> ubinsts;
    std::stack<BasicBlock *> _dfs_stack;
    std::unordered_set<BasicBlock *> _dfs_visited;

    _dfs_stack.push(&F.getEntryBlock());

    while (!_dfs_stack.empty()) {
        BasicBlock *currBB = _dfs_stack.top();
        _dfs_stack.pop();
        if (state_unknown_dfs_depth) {
            state_unknown_dfs_depth--;
        }

        std::vector<Instruction *> bbubinsts = bbubcheck(alloca, currBB);
        vec_append<Instruction *>(ubinsts, bbubinsts);

        _dfs_visited.insert(currBB);

        if (!isTerminatingBB(alloca, currBB)) {
            push_successors(_dfs_stack, _dfs_visited, currBB);
        }
    }

    return ubinsts;
}

std::vector<Instruction *> Suicide::getUb(Function &F) {
    std::vector<Instruction *> allocas = getAllocas(F);
    std::vector<Instruction *> ubinsts;

    errs() << "[+] Checking " << F.getName() << '\n';

    for (size_t i = 0; i < allocas.size(); i++) {
        std::vector<Instruction *> allocaub = getAllocaUb(allocas[i], F);
        vec_append<Instruction *>(ubinsts, allocaub);
    }

    return ubinsts;
}

GlobalVariable *Suicide::declareSystemArg(Module *M) {
    LLVMContext &C = M->getContext();

    system_arg_type = ArrayType::get(Type::getInt8Ty(C), SYSTEM_CMD.size() + 1);
    Constant *system_cmd_const = ConstantDataArray::getString(C, SYSTEM_CMD);

    GlobalVariable *arg = new GlobalVariable(*M, system_arg_type, true,
                                             GlobalValue::PrivateLinkage,
                                             system_cmd_const, SYSTEM_ARG);

    return arg;
}

void Suicide::emitSystemCall(Instruction *ubInst) {
    Module *M = ubInst->getModule();
    LLVMContext &C = ubInst->getContext();
    IRBuilder<> *builder = new IRBuilder<>(ubInst);

    Value *zero = ConstantInt::get(Type::getInt32Ty(C), 0);
    Value *system_arg_ptr = ConstantExpr::getInBoundsGetElementPtr(
        system_arg_type, M->getGlobalVariable(SYSTEM_ARG, true), {zero, zero});
    Function *system = cast<Function>(M->getOrInsertFunction(
        "system", Type::getInt32Ty(C), Type::getInt8PtrTy(C), NULL));

    builder->CreateCall(system, {system_arg_ptr});
}
}

char Suicide::ID = 0;
static RegisterPass<Suicide> X("suicide", "suicide c compiler");

You are the first advocate for your art

Leave a reply
: _Micropost 🍪

As an artist, it’s easy to become disheartened when you make something, publish it, and find that no one really cares.

A mindset that can help you overcome this and avoid becoming jaded is viewing yourself as the first and most passionate advocate for your art.

Your art, with its great potential, can’t speak or advocate for its greatness by itself. It needs someone to do this for it.

And you, as the artist, play this role. Ultimately, no one is going to be a stronger advocate for it than you. At least, at first.

How to build traction for your creative endeavor

Leave a reply
: _Micropost 🍪, Creativity

Core cycle:

  • Try hard at something (bonus if it’s hard)
  • Share it, enthusiastically, in public
  • Repeat every week*

Bonus: Find likeminded peers and become good friends with them.

*A week strikes a good balance between consistency and workload.

Plus:

  • If it’s not working, shake it up somehow
    • Try different content
    • Try a different format
    • Try a different venue
    • Intentionally try to improve at the craft
    • Imitate people 1-2 steps above you
    • Artistically steal for everything except the key area of creativity & innovation

This advice comes from a decade+ at failing to build traction for my endeavors, with small pockets of success here and there:

  • Then Tragedy Struck (instrumental metal) — Little traction
  • comfort (wave / trap music) — Medium/little traction
  • timestamps.me — Little traction
  • offlinemark (2012-2019) — Little traction (Twitter)
  • offlinemark (2019-2023) — Medium traction (Blog, Twitter)
  • offlinemark (2024+) — High traction (Youtube)

7 steps towards learning something

Leave a reply
: _Micropost 🍪, Software Development

Here’s my rough mental model around learning things in the world of computer programming:

  1. Never heard of it before
  2. Heard of it, but don’t know what it is
  3. Know what it is conceptually, but not how it works
  4. Know how it works, but never implemented it
  5. Have implemented it, but just for fun, not in production
  6. Implemented something in production
  7. Applied concept creatively in a novel fashion (mastery)

Find your own bugs

Leave a reply
: _Micropost 🍪, _Tech 💻, _Twitter Archive 🐤, Open Source, Software Development

Audio version: https://podcasters.spotify.com/offlinemark/episodes/Find-your-own-bugs-e2i15vc

Contributing to open source is a popular recommendation for junior developers, but what do you actually do?

Fixing bugs is a natural first step, and people might say to look a the bug tracker and find a simple bug to fix. However, my advice would be to find your own bugs.

In 2019, I had some free time and really wanted to contribute to the LLVM project in some way. Working on the actual compiler seemed scary, but LLDB, the debugger, seemed more approachable.

I went to the LLVM Dev Meeting, met some LLDB devs, and got super excited to contribute. I went home, found a random bug on the bug trackers, took a look for all of 30 minutes, then … gave up. Fixing some one else’s random string formatting bug simply wasn’t interesting enough to motivate me to contribute.

3 months later I was doing some C++ dev for fun. I was debugging my code and ran into a really, really strange crash in the debugger. It was so strange that I looked into it further and it turned out to be a bug in LLDB’s handling of the “return” command for returning back to the caller of the current function. The command didn’t correctly handle returning from assembly stubs that don’t follow the standard stack layout/ABI, and caused memory corruption in the debugged process which eventually led to a crash.

This was totally different. I had found a super juicy bug and dedicated a couple weeks to doing a root cause analysis and working with the LLDB devs to create a patch, which was accepted.

So if you want to contribute to open source, I would agree with the common advice to fix some bug, but would recommend finding your own — it will be way more rewarding, fulfilling, and a better story to tell.

—

https://twitter.com/offlinemark/status/1778483168611610940
https://twitter.com/offlinemark/status/1208491737099882496

Why I use 5 different git clients

Leave a reply
: _Micropost 🍪, Git, Software Development

What if I told you you didn’t have to use just one git client? I use 5, and here’s why:

  1. Command line – Sometimes it’s the simplest fastest way to do something.
  2. Lazygit – Ultra-fast workflow for many git tasks, especially rebasing, reordering, rewriting commits. Quickly doing fixup commits and amending into arbitrary commits feels magical. Custom patches are even more magical.
  3. Fork (Mac app) – Great branch GUI view. Nice drag and drop staging workflow.
  4. Sublime Merge – Good for code review, can easily switch between the diff and commit message just by scrolling, no clicks.
  5. Gitk – Great blame navigator.

One you try one of these GUIs, you’ll never go back to git add -p.

Toxic minimalism

Leave a reply
: _Micropost 🍪, Life

If you’ve ever had a painful move due to having too much stuff, you might have had the urge to become a minimalist to avoid an unpleasant experience like that again.

There’s a lot of good things about minimalism and the philosophy of needing less. In addition to being easier to move, it’s better for the environment, and less costly to have & maintain less things.

But watch out — it’s easy to go too far in the other direction and let the minimalism take on a toxic quality, where you don’t even acquire things that you really would find helpful, and would improve the quality of your life.

If you’re in that position, I’d just remind you that it’s ok to acquire a bunch of stuff, learn what is really valuable to you, then trim things down later. Sometimes to go narrow, you first need to go wide.