ELI5: Capability-based systems

This post on capabilities says there isn’t a “good, basic introduction to capabilities”, then proceeds to write 13,000 words of incomprehensible gibberish. Having spent some time reading about capabilities I can say this is actually the least bad explanation I’ve yet seen. This community could write a 100 page manual for a toaster that would confuse a physicist.

Capabilities are a simple and obvious design pattern from object-oriented programming that can be applied more broadly. The simplest example is a file system. Here’s some python-ish pseudocode to describe the objects and what they are capable of doing.

class Directory:
    def name() -> str: ...
    def create_dir(name: str) -> Directory: ...
    def create_file(name: str) -> File: ...
    def __iter__() -> Union[Directory, File]:
        yield every directory or file under here

class File:
    def name() -> str: ...
    def open(): ...
    def close(): ...
    def read() -> bytes: ...
    def write(data: bytes): ...
    def append(data: bytes): ...
    def delete(): ...
    def size() -> int: ...

When your program starts it is somehow given an instance for your home directory. Call homedir.create_file("blog_post") to create an instance of a File object. Call open on the File instance, then write stuff to the file. Finally close the file when you’re done. The fact that you have instances of these objects means you have permission to do these operations. The OS doesn’t need to check anything.

Contrast this with the Unix creat function. You’d write creat("/home/me/blog_post", S_IRWXU) and the kernel would have to check if you have permission to create that file. Even a call to fread(buffer, 1, 10, file_handle) would need to verify that file_handle is valid and you have permission to read from it. Remember that file_handle is an unsigned int. You can put any number there, valid or not.

The difference between these two models of a filesystem is already significant. In the Unix model, every operation must be checked by the kernel to ensure you have permission. In the OO model, if you have an instance then you can call any of its operations.

What if I want to create a file strictly for logging? Then I only want the logging system to append data to a file. We can use the delegation pattern to implement that.

def LogFile:
    private real_file
    def __init__(real_file: File): ...
    def open(): real_file.open()
    def close(): real_file.close()
    def append(data: bytes): real_file.append(data)
    def size() -> int: real_file.size()

I’ll pass an instance of this file to my logging software. This restricts the logger to only performing these operations on the specific file to which I’ve delegated. The logger can’t delete the file or look around the directory, and the kernel doesn’t need to check anything. Furthermore, if the logger passes this file to another process, it also can’t do more than append.

What if I want to limit the size of the log file so it doesn’t fill up my disk? I can add some logic to my wrapper class to cap the size of the file.

def CappedLogFile:
    private log_file
    def __init__(log_file: LogFile): ...
    def open(): log_file.open()
    def close(): log_file.close()
    def append(data: bytes) -> bool:
        if log_file.size() < 100MB:
            return True
            return False

What if I want to rotate logs? Then I can combine objects to create smarter behavior:

def RotateLogFile:
    private log_dir, log_name
    private curr_file: int, log_files: List[CappedLogFile]
    def __init__(log_dir: Directory, log_name: str):
        for i in range(5):
            log_files.append(CappedLogFile(LogFile(log_dir.create_file(log_name + str(i)))))
        curr_file = 0
    def open(): log_files[curr_file].open()
    def close(): log_files[curr_file].close()
    def append(data: bytes):
        if not log_files[curr_file].append(data):
            curr_file = (curr_file + 1) % 5   # rotate file
            log_files[curr_file] = log_dir.create_file(log_name + str(curr_file))
            return log_files[curr_file].append(data)
        return True

The central idea of capability-based systems is every resource (e.g. file) has a set of capabilities (open, close, …). If you have the object then you can call its methods. The kernel never has to check if a process is authorized to do something. To reduce what an object can do you just encapsulate it. To build something fancier, it’s just OO programming.

Despite being relatively simple, it’s actually difficult to implement when the underlying OS doesn’t use capabilities. The file API for Unix passes around file handles, which are really unsigned ints. You could pass in arbitrary numbers and try to trick the OS. To use capabilities we’d need the OS to return a file handle that can’t be faked. Furthermore, you should be able to create an object like LogFile and send it to another process. That process should think it’s just another file handle. Take a look at chapter 3 of the seL4 OS manual. Also see Midori at Microsoft.

Capabilities become more interesting when you think about distributed services that call each other. Now you can’t pass around Python objects to represent the resource and it’s API. You need something else to tell a service “I am authorized to delete all DB tables.” And you need to be able to convert that capability to “I can delete temp DB tables.”

So there’s a high-level explanation in 1000 words.