LWN.net Weekly Edition for April 14, 2022

Welcome to the LWN.net Weekly Edition for April 14, 2022

This edition contains the following feature content:

• A literal string type for Python: a new LiteralString type to help fend off SQL-injection (and other) vulnerabilities.
• trusted_for() bounces off the merge window: functionality to allow tools to ask the kernel if a file is "trusted" (for execution) fails to land in 5.18.
• Private memory for KVM guests: providing a way for KVM guests to have memory that the hypervisor and kernel cannot see.
• Negative dentries, 20 years later: looking for a way to solve a longstanding problem with the negative dentry cache growing too large.
• Readahead: the documentation I wanted to read: improving the documentation on the kernel's mechanism to read data before it is explicitly requested.

This week's edition also includes these inner pages:

• Brief items: Brief news items from throughout the community.
• Announcements: Newsletters, conferences, security updates, patches, and more.

Please enjoy this week's edition, and, as always, thank you for supporting LWN.net.

Comments (none posted)

A literal string type for Python

Using strings with contents that are supplied by users can be fraught with peril; SQL injection is a well-known technique for attacking applications that stems from that, for example. Generally, database frameworks and libraries provide mechanisms that seek to lead programmers toward doing The Right Thing, with parameterized queries and the like, but they cannot enforce that—inventive developers will seemingly always find ways to inject user input into places it should not go. A recently adopted Python Enhancement Proposal (PEP) provides a way to enforce the use of strings that are untainted by user input, but it uses the optional typing features of the language to do so; those wanting to take advantage of it will need to be running a type-checking program.

PEP 675 ("Arbitrary Literal String Type") flew under the radar to a certain extent. It was discussed on the Python typing-sig mailing list, mostly back in January of this year, then posted to the python-dev mailing list in February, where there was little discussion. In March, it was accepted by the steering council for inclusion into Python 3.11, which is due in October. Gregory P. Smith had some interesting thoughts when he announced the acceptance on behalf of the council:

TL;DR - PEP 675 allows type checkers to help prevent bugs allowing attacker-controlled data to be passed to APIs that declare themselves as requiring literal, in-code strings.

This is a very thorough PEP with a compelling and highly relevant set of use cases. If I tried to call out all the things we like about it, it'd turn into a table of contents. It is long, but everything has a reason to be there. :)

Once implemented, we expect it to be a challenge to tighten widely used existing APIs that accept str today to be LiteralString for practical reasons of what existing code calling unrestricted APIs naturally does. The community would benefit from anyone who attempts to move a widely used existing str API to LiteralString sharing their experiences, successful or not.

As he notes, the feature will not magically fix SQL-injection vulnerabilities (or other, similar problems); it will take time to properly annotate existing APIs, for one thing. Beyond that, applications will need to be processed using one of the available Python static type checkers (e.g. mypy or pytype) and then be fixed to no longer work around the restrictions on passing literal strings.

SQL injection

The Motivation section of the PEP describes the problem well; here we adapt and condense some of its examples. Code vulnerable to a SQL injection might look something like the following:

    def query_user(conn: Connection, user_id: str) -> User:
	query = f"SELECT * FROM data WHERE user_id = {user_id}"
	conn.execute(query)
        ...

    query_user(conn, "user123")
    query_user(conn, "user123; DROP TABLE data;")
    query_user(conn, "user123 OR 1 = 1")

The query_user() function may seem reasonable at first glance and the first use of it works just fine. The other two show how the call could be misused if, for example, the user to be searched for is being read from a web form. The second call would delete the data table, while the third would retrieve all users (since 1 = 1 is always true). Anyone running a web application on today's web will be all-too-familiar with messages in their logs showing efforts to exploit this kind of problem. Of course, xkcd has also highlighted the problem in its inimitable style.

Database libraries generally have a mechanism to avoid that kind of programming error through the use of query parameters. For example:

    def query_user(conn: Connection, user_id: str) -> User:
        query = "SELECT * FROM data WHERE user_id = ?"
        conn.execute(query, (user_id,))
        ...

When developers use that mechanism, the database library makes the substitution for "?" in a safe way; instead of tacking on the extra stuff as additional SQL, it will look for users with names that are exactly what is in the string passed to query_user(). If developers would use query parameters everywhere, the problem would largely be solved, but the library cannot enforce that type of usage. It simply gets a string that it needs to execute; the library's documentation can admonish developers not to dynamically build the query string with user input, but that clearly has not stopped them from doing so.

So the PEP adds a LiteralString type to the typing module to allow developers to annotate variables, function parameters, return values, and more to indicate that the string value must be composed of literal values. So, as an example from the PEP shows, the execute() member function for a database API might be defined as follows:

    from typing import LiteralString

    def execute(self, sql: LiteralString, parameters: Iterable[str] = ...) -> Cursor: ...

That would cause uses of non-literal strings as parameters to the function to provoke a warning or error from the type checker:

    def query_user(conn: Connection, user_id: str) -> User:
	query = f"SELECT * FROM data WHERE user_id = {user_id}"
	conn.execute(query)
	# Error: Expected LiteralString, got str.

In this example, the query string has been built from other data, thus it may be susceptible to SQL-injection problems. An interpolated Python f-string is not a literal string if it is built with regular str variables, so a type checker can infer that query is not either, thus it can complain. There is a somewhat common pattern, which is often completely benign, that the PEP also takes into account. For example:

    def query_user(conn: Connection, user_id: str, limit: bool) -> User:
        query = "SELECT * FROM data WHERE user_id = ?"
	if limit:
	    query += " LIMIT 1"
	    
        conn.execute(query, (user_id,))

In that version of query_user(), query is still a LiteralString even after the limit clause has been appended, because concatenating two LiteralString types is a LiteralString. One could even expand that further by turning the "LIMIT 1" into "LIMIT ?" and building up a list of parameter values to pass to execute(). Well-written code already does those sorts of things, so the adjustment to the addition of LiteralString annotations should be minimal—for those code bases, at least. Those projects will benefit when someone slips up and inserts a potential injection into the code; the next time the type checker is run, it will loudly point out the problem.

Meanwhile, the technique can be applied more widely, as the PEP indicates:

LiteralString is also useful in other cases where we want strict command-data separation, such as when building shell commands or when rendering a string into an HTML response without escaping (see Appendix A: Other Uses). Overall, this combination of strictness and flexibility makes it easy to enforce safer API usage in sensitive code without burdening users.

Why use a type?

At first glance, using the type system to enforce this kind of behavior might seem like an odd choice, but the Rationale section of the PEP describes the other options and shows why the type system actually makes the most sense, at least for Python. A run-time approach would need to rely on heuristics that are imperfect (and highly use-case dependent). A static analyzer that looked at the abstract syntax tree to try to spot problems of this sort would be overly restrictive because it cannot determine "when a string is assigned to an intermediate variable or when it is transformed by a benign function". The type checker is better placed:

The type checker, surprisingly, does better than both because it has access to information not available in the runtime or static analysis approaches. Specifically, the type checker can tell us whether an expression has a literal string type, say Literal["foo"]. The type checker already propagates types across variable assignments or function calls.

The Literal type has been present since Python 3.8. It allows specifying the legal values for a given type; for example, a parameter that can only be a few specific values might be: Literal["a", "b", "c"]. A parameter of that type that was passed "d" would fail the type check, as would passing a regular string type:

    def foo(x: Literal["a", "b"]) -> None: ...

    foo("a")               # works
    a_var = "a string"
    foo(a_var)             # type failure

So Literal might be useful in parts of the application, but a SQL query can contain any string, so LiteralString was born:

LiteralString is the "supertype" of all literal string types. In effect, this PEP just introduces a type in the type hierarchy between Literal["foo"] and str. Any particular literal string, such as Literal["foo"] or Literal["bar"], is compatible with LiteralString, but not the other way around. The "supertype" of LiteralString itself is str. So, LiteralString is compatible with str, but not the other way around.

Due to overloading the types allowed for many of the standard str methods, as described in Appendix C, the LiteralString type can be preserved through various kinds of string transformations. For example:

    def bar(x: LiteralString, y: LiteralString) -> LiteralString:
        return ", ".join(x,y)

That works to join the two parameters with a ", " because that separator string is literal, as it is not composed from other strings, and the join() arguments also have the type LiteralString. It might seem like the language is "casting" the value to the return type, but that is not happening here; Python type annotations are not used by the language at run time. That kind of type overloading also applies to f-strings, so those can still produce a LiteralString:

    def baz(x: List[LiteralString], y: List[LiteralString]) -> LiteralString:
        xout = " ".join(x)
	yout = "+".join(y)
	return f"({xout}) '{yout}'"

    baz(["a", "b"], ["c", "d"])    # produces "(a b) 'c+d'" as a LiteralString

So the two lists of literal strings are combined using join() and an f-string to produce something that is still a LiteralString. There is a multi-line example of using that in SQL-query context in the Rejected Alternatives section of the PEP; it turns out that some existing tools for catching SQL-injection errors cannot support that kind of benign query-string construction. Note that the first example in the article could perhaps be made to "work" by declaring user_id as a LiteralString instead of a str, though passing data that came in from the outside would fail a type check without some kind of gyrations by the programmer.

Those kinds of gyrations are explicitly listed in the Limitations section. There will always be ways to evade the checks—by not running a type checker to start with—but the PEP is not meant to stop that kind of thing:

[...] ultimately a clever, malicious developer attempting to circumvent the protections offered by LiteralString will always succeed. The important thing to remember is that LiteralString is not intended to protect against malicious developers; it is meant to protect against benign developers accidentally using sensitive APIs in a dangerous way (without getting in their way otherwise).

Without LiteralString, the best enforcement tool API authors have is documentation, which is easily ignored and often not seen. With LiteralString, API misuse requires conscious thought and artifacts in the code that reviewers and future developers can notice.

Reception

In a reply to the announcement of the PEP's acceptance, Neil Schemenauer applauded the idea, noting that he had done something along the same lines years ago:

I did something like this for HTML templating in the Quixote web framework (to avoid XSS [cross-site scripting] bugs). I did it as a special kind of module with a slightly different compiler (using AST transform). With the LiteralString feature, I can implement the same kind of thing directly in Python.

Quixote has an htmltext class for strings that are considered safe because they have already been properly escaped for HTML, unlike regular strings which are generally treated as still needing to be escaped. The template system that he describes provides a way to generate HTML directly from functions, while escaping parameters and the like, so that cross-site scripting problems are avoided. Quixote was one of the earlier Python web frameworks and is still in use, including on this site.

Unlike with some other PEPs, there has not been a lot of discussion of its merits of the idea or changes needed in the text of the PEP. Some of that was done in the typing-sig thread, but much of it was something of a bikeshed exercise for the name of the type. As Smith noted, the PEP authors, Pradeep Kumar Srinivasan and Graham Bleaney, along with the core developer sponsor, Jelle Zijlstra, have done a nice job in creating a compelling case for the feature. In addition, they did so in a way that allows well-behaved code to just continue to work.

Over the years, the Python typing features have grown and matured since their introduction as "type hints" back in 2014. PEP 484 ("Type Hints") added the feature to Python 3.5 and every release since then has added more to the feature. There is a long list of typing PEPs that have been adopted; PEP 675 will soon join the party.

While the typing features (and the use of type checkers) is optional for Python, the language is clearly headed toward more widespread use of types. The rise of typed Python has led to some discomfort in the ecosystem that types are starting a slow move toward dominating decisions for the language—to the point where those who are not interested in types, per se, are being left behind. So far, at least, that does not really seem to be the case; the steering council has been trying to balance the needs of the different groups of users and has generally been successful in doing so.

There are, of course, many constituents in the pro-type camp. Some larger applications have already retrofitted type features into their code and more of that work is ongoing. Any new Python project, especially one that looks likely to grow into a significant code base, should likely carefully consider adding a type checker into the mix. There are, it seems, lots of benefits and few real downsides at this point. LiteralString will only add to those benefits over time.

Comments (17 posted)

trusted_for() bounces off the merge window

When last we looked in on the proposed trusted_for() system call, which would allow user-space interpreters and other tools to ask the kernel whether a file is "trusted" for execution, it looked like it was on-track for the mainline. That was back in October 2020; the patch has been updated multiple times since then, made its way into linux-next, and a pull request was made by Mickaël Salaün for the 5.18 merge window. But it seems that there will be more to the story of getting this functionality into the kernel, as Linus Torvalds declined to pull trusted_for(), at least partly because he did not like the name, but there were other reasons as well. While he is not opposed to the functionality it would provide, he also had strong feelings that a new system call was not the right approach.

Background

The patch has been through 18 versions since it was first introduced in 2018. It started out as a new flag (O_MAYEXEC) for the openat2() system call. The idea behind it is fairly straightforward: the kernel enforces a number of security checks on files before they can be executed, but various kinds of tools can simply read files in order to execute them. Those files are not subject to the same checks, since the kernel is unaware that they contain code to be executed; finding a way to apply the same checks to files that are, effectively, being opened for execution, is the goal of Salaün's work.

Obviously, user space needs to be involved since the kernel cannot know that any file being opened is going to be used that way—the vast majority of files are not, after all. Python and other tools are interested in supporting security checks for files containing code (see PEP 578, for example), but there will clearly be a long tail of tools needing to inform the kernel of their intention and some may well resist or be uninterested in doing so. There would be value in having the feature for some types of locked-down systems that only have "well-behaved" tools that make the check.

Along the way, Al Viro, maintainer of the virtual filesystem (VFS) layer, complained that openat2() was not the proper place for handling this kind of check. He suggested a new system call, instead. The next version of the patches moved to an AT_INTERPRETED flag for the faccessat2() system call instead, but Viro thought that was not any better and again suggested a new system call.

After a round of bikeshedding about the name, Salaün decided on trusted_for(). The subsequent revisions were mostly cosmetic changes or updating the code for more recent kernels. It looks nearly the same as it did in our article a year and a half ago:

    int trusted_for(const int fd, const int usage, const unsigned int flags);

The call will check the file indicated by fd to see if it is allowed for the usage (TRUSTED_FOR_EXECUTION is the only option currently defined); flags is, as yet, unused. It will return zero if the file is trusted or EACCESS if it is not. By default, however, trusted_for() does not actually do anything, but there is a new fs.trusted_for_policy sysctl knob that can be set to have it check for files on a filesystem mounted with noexec, files that do not have execute permission, or both.

No merge

After the 5.18 merge window had closed without trusted_for() being pulled, both Salaün and Kees Cook asked about the status. It turns out that Torvalds was not happy to see a new, non-standard system call with a "completely random interface with no semantics except for random 'future flags'". Salaün disagreed that the semantics were unspecified; "I think the semantic is well defined: 'This new syscall enables user space to ask the kernel: is this file descriptor's content trusted to be used for this purpose?'"

Torvalds had a few other complaints as well:

What the system call seems to actually *want* is basically a new flag to access() (and faccessat()). One that is very close to what X_OK already is.

[...] No way will this ever get merged, and whoever came up with that disgusting "trusted_for()" (for WHAT? WHO TRUSTS? WHY?) should look themselves in the mirror.

If you add a new X_OK variant to access(), maybe that could fly.

The X_OK flag for access() (and faccessat2()) is used to determine whether the process has permission to execute a given file, using the real user and group IDs (rather than the effective IDs, which could be different for set-user-ID programs). For faccessat2(), the AT_EACCESS flag can be used to check the effective IDs instead. As Salaün noted, though, Torvalds's suggestion was similar to what Salaün had earlier done with AT_INTERPRETED for faccessat2(); he is willing to go back to that mechanism and wondered if Torvalds liked that approach better.

Torvalds looked at the earlier patch, which he said was a more reasonable approach, though he had some specific questions and suggestions. He wondered why a new mode bit, perhaps called EXECVE_OK, could not be used instead of adding the new AT_INTERPRETED flag value. That way it could be used for both access(), which lacks a flags parameter, and for faccessat2(); that makes more sense given what is being checked. The currently defined mode bits for those system calls check for read, write, or execute access.

Salaün agreed that using a mode bit was a better choice. Some of the other oddities that Torvalds noted in the patch were due to it being an early version of the feature on a path that was quickly abandoned after Viro's objection. Salaün plans to update the patch and resubmit, though one might guess Viro will still have the same objections, so how far it all goes is not clear. In addition, if further checks are added, such as for Linux security module (LSM) access restrictions or file-integrity verification, it may be done by way of additional bits on fs.trusted_for_policy (with a new name), but it will require additional code for access()/faccessat2() to actually perform the checks.

Bikeshed history

Ted Ts'o suggested that the history of the evolution of the feature would be a good addition to the changelog:

As a suggestion, something that can be helpful for something which has been as heavily bike-sheded as this concept might be to write a "legislative history", or perhaps, a "bike shed history".

And not just with links to mailing list discussions, but a short summary of why, for example, we moved from the open flag O_MAYEXEC to the faccessat(2) approach. I looked, but I couldn't find the reasoning while diving into the mail archives. [...]

It might be that when all of this is laid out, we can either revisit prior design decisions as "that bike-shed request to support this corner case was unreasonable", or "oh, OK, this is why we need as fully general a solution as this".

Some of that information is contained in the patch that actually adds the system call, though it mostly just lists the changes for each version without a lot of explanation of the sort Ts'o is looking for. This article and the earlier two may also help fill in some of those holes.

Overall, it is a fairly simple feature that could provide some useful functionality in specialized environments. But where it actually will live has been rather difficult to resolve. Given Torvalds's preference, returning to the plan for putting it in access() and faccessat2() looks like it has a plausible future, but we will have to see how version 19 (and beyond) of the patch set fare.

Comments (9 posted)

Private memory for KVM guests

Cloud computing is a wonderful thing; it allows efficient use of computing systems and makes virtual machines instantly available at the click of a mouse or API call. But cloud computing can also be problematic; the security of virtual machines is dependent on the security of the host system. In most deployed systems, a host computer can dig through its guests' memory at will; users running guest systems have to just hope that doesn't happen. There are a number of solutions to that problem under development, including this KVM guest-private memory patch set by Chao Peng and others, but some open questions remain.

A KVM-based hypervisor runs as a user-space process on the host system. To provide a guest with memory, the hypervisor allocates that memory on the host, then uses various KVM ioctl() calls to map it into the guest's "physical" address space. But the hypervisor retains its mapping to the memory as well, with no constraints on how the memory can be accessed. Sometimes that access is necessary for communication between the guest and the hypervisor, but the guest would likely want to keep much of that memory to itself.

Providing private memory

The proposed solution to this problem makes use of the kernel's memfd mechanism. The hypervisor can set up a private memory area for its guest by calling memfd_create() with the new MFD_INACCESSIBLE flag. That creates a special type of memfd that the creator can do little with; attempts to read from or write to it will fail, as will attempts to map it into memory. The creator can, though, use fallocate() to allocate (inaccessible) pages to this memfd. If the MEMFD_SECRET flag is also used at creation time, then the host's direct mapping for the affected pages will be removed, meaning that the host kernel, too, will have no mapping for that memory, making it difficult to access even if the host kernel is compromised.

The one other thing that can be done with it is to pass it to KVM to map into the guest's virtual address space. The guest will then have full access to this memory, even though the host (which set it up) does not. Enabling this functionality requires setting up callbacks in both directions between KVM and the backing store (probably shmfs) that actually provides the memory. The first set of operations is provided on the KVM side:

    struct memfile_notifier_ops {
	void (*invalidate)(struct memfile_notifier *notifier,
			   pgoff_t start, pgoff_t end);
	void (*fallocate)(struct memfile_notifier *notifier,
			  pgoff_t start, pgoff_t end);
    };

The fallocate() function will be called whenever memory is mapped into this memory range — when the fallocate() system call is used on the host side. It's worth noting that Dave Chinner objected to this name, so this callback is likely to end up being named something like notify_populate() instead. The invalidate() callback, instead, is used to indicate that a range of pages has been removed and can no longer be accessed from the guest.

The other callbacks are supplied by the backing-store implementation to provide KVM with access to the memory in this otherwise inaccessible memfd:

    struct memfile_pfn_ops {
	long (*get_lock_pfn)(struct inode *inode, pgoff_t offset, int *order);
	void (*put_unlock_pfn)(unsigned long pfn);
    };

KVM will call get_lock_pfn() to obtain the host page-frame number(s) for one or more pages. When KVM unmaps pages, it calls put_unlock_pfn() to inform the backing store that those pages are no longer being used.

This mechanism, along with the requisite plumbing in KVM, is enough to provide private memory to a guest. The hypervisor will allocate that memory for the guest, but will not be able to access it in any way.

Conversion

Quentin Perret raised a relevant question: what happens when the guest wants to share some of its private memory with the host? This happens reasonably frequently (to set up I/O buffers, for example), so most solutions in this area provide a mechanism for the "conversion" of memory pages between the private and shared states. Perret asked how that was meant to be handled with this mechanism.

The answer, as provided by Sean Christopherson, is that the guest indicates the desire to convert pages by exiting back into the hypervisor with a KVM_EXIT_MEMORY_ERROR status. That status will be passed back to the hypervisor process [Update: Thanks to Paolo Bonzini, we have a corrected version of this explanation below. ]

The answer, as provided by Sean Christopherson, is that the guest indicates the desire to convert pages with a hypercall. The KVM_RUN ioctl() immediately returns with a KVM_EXIT_MEMORY_ERROR status to the user-space hypervisor process; if it concurs with the request, it responds by unmapping the relevant section of the inaccessible memfd. That, too, is done with fallocate(), using the "hole-punch" functionality. The hypervisor can then map ordinary memory into the newly created hole, resulting in a range that is accessible to both sides.

An important thing to note is that sharing pages back to the host is, by design, a destructive operation; the hole-punch operation will cause the data that was stored there to go away. As Christopherson described, this behavior matches what is done by a number of hardware implementations; pages must be shared with the host before being filled with the data to be shared. Perret, who is working on a similar mechanism for Android ("protected KVM" or pKVM), would rather have an in-place conversion mechanism available; without that, he said, this solution "might not suit pKVM all that well". He gave a list of reasons why that would be useful, including:

One goal of pKVM is to migrate some things away from the Arm Trustzone environment (e.g. DRM and the likes) and into protected VMs instead. This will give Linux a fighting chance to defend itself against these things -- they currently have access to _all_ memory. And transitioning pages between Linux and Trustzone (donations and shares) is fast and non-destructive, so we really do not want pKVM to regress by requiring the hypervisor to memcpy things.

Christopherson questioned the need for non-destructive conversions, suggesting that reworking pKVM to handle destructive conversions "doesn't seem too onerous". Andy Lutomirski was also unclear on the benefits of that capability, and worried about the difficulty of implementing it correctly:

If we actually wanted to support transitioning the same page between shared and private, though, we have a bit of an awkward situation. Private to shared is conceptually easy -- do some bookkeeping, reconstitute the direct map entry, and it's done. The other direction is a mess: all existing uses of the page need to be torn down. If the page has been recently used for DMA, this includes IOMMU entries.

Perret reiterated his feeling that in-place conversion would perform better, but admitted that he (like all other participants in the discussion) has not yet collected the numbers to prove that one way or the other. He also doesn't have the details of in-place conversion worked out, though he proposed an outline for how it could work.

As of this writing the conversation is ongoing with no clear resolution in sight. The developers involved all have an interest in creating a mechanism that will work for all use cases; there is little interest in adding several private-memory implementations. But they all want to also get the best performance they can while avoiding excess complexity. Reconciling objectives like these is at the core of system programming (and, for that matter, most other types of programming) and is something that the kernel community is usually reasonably good at — at least, if all of the interested parties are participating in the discussion. The developers have begun to talk so, with luck, a workable solution can be expected to emerge from this conversation, but it may take a while yet.

Comments (8 posted)

Negative dentries, 20 years later

Filesystems and the virtual filesystem layer are in the business of managing files that actually exist, but the Linux "dentry cache", which remembers the results of file-name lookups, also keeps track of files that don't exist. This cache of "negative dentries" plays an important role in the overall performance of the system but, if it is allowed to grow too large, its role can become negative in its own right. As the 2022 Linux Storage, Filesystem, and Memory-Management Summit (LSFMM) approaches, the subject of negative dentries has come up yet again; whether one can be positive about the prospects for a resolution this time around remains unclear.

The kernel's dentry cache saves the results of looking up a file in a filesystem. Should the need arise to look up the same file again, the cached result can be used, avoiding a trip through the underlying filesystem and accesses to the storage device. Repeated file-name lookups are common — consider /usr/bin/bash or ~/.nethackrc — so this is an important optimization to make.

The importance of remembering failed lookups in negative dentries may be less obvious at the outset. As it happens, repeated attempts to look up a nonexistent file are also common; an example would be the shell's process of working through the search path every time a user types "vi" (Emacs users start the editor once and never leave its cozy confines thereafter, so they don't benefit in the same way). Even more common are failed lookups created by the program loader searching for shared libraries or a compiler looking for include files. One is often advised to "fail fast" in this society; when it comes to lookups of files that don't exist, that can indeed be good advice.

So negative dentries are a good thing but, as we all know, it is possible to have too much of a good thing. While normal dentries are limited by the number of files that actually exist, there are few limits to the number of nonexistent files. As a result, it is easy for a malicious (or simply unaware) application to create negative dentries in huge numbers. If memory is tight, the memory-management subsystem will eventually work to push some of these negative dentries out. In the absence of memory pressure, though, negative dentries can accumulate indefinitely, leaving a large mess to clean up when memory does inevitably run out.

Some kernel problems are resolved quickly; others take a little longer. LWN briefly reported on a complaint about the memory consumption of negative dentries back in 2002, nearly exactly 20 years ago. A more recent attempt to solve the problem was covered here in early 2020. While numerous developers have taken a stab at the negative-dentry problem over time, the core problem remains. Those dentries still take up valuable memory, and they can create other problems (such as soft lockups) as well.

A new discussion

In mid-March, Matthew Wilcox suggested that the negative-dentry problem might make a good LSFMM topic: "maybe some focused brainstorming on the problem would lead to something that actually works". Often, simply proposing a topic like this can elicit the sort of brainstorming needed to work toward a solution. That didn't happen this time, but it did lead to the posting of a patch set by Stephen Brennan showing a new approach to the problem.

One of the difficulties posed by the negative-dentry problem is that it can be hard to know when the time has come to start throwing them away. The sizes of systems and workloads vary hugely, so any sort of simple limit is likely to cause performance regressions somewhere. Providing a knob for the system administrator to tune the limit can be tempting, but that just pushes the problem onto the users, and it is generally felt that the kernel should be able to figure things out by itself. But, as Brennan noted, that is not easy:

It's hard to look at a hash bucket or LRU list and design a heuristic for an acceptable amount of negative dentries: it won't scale from small to large systems well. But setting up heuristics on a per-directory basis will scale better, and it's easier to reason about.

The specific heuristic proposed by the patch is that the negative dentries for any given directory should not outnumber the positive dentries by more than a factor of five. If there are 20 positive dentries in the cache for a directory, there can be no more than 100 negative dentries. It is a nice idea, with only one small problem: the kernel doesn't keep counts of the number of dentries (or their types) associated with each directory.

To get around that, Brennan added code that maintains a "cursor" in the list of dentries associated with each directory. Whenever a dentry operation (creation or deletion) happens, that code will advance the cursor through the next six dentries in the list; if it does not encounter at least one positive dentry, it assumes that the limit has been exceeded and cleans up some negative dentries. Attaching this work to the dentry operations themselves means that the penalty will be paid by processes that are responsible for the creation of a lot of dentries, which seems correct.

The problem with this approach is, of course, that there is nothing that forces dentries to be added to a directory's list in any particular order. Depending on the order in which dentries are created, this algorithm could come to an incorrect conclusion regarding the real ratio of positive to negative dentries and do the wrong thing. Brennan acknowledged this problem ("This workload-dependence is bad, full stop"), but has not yet come up with a better idea. As things stand, this algorithm seems certain to lead to pathological cases; that may prevent the acceptance of this patch set even in the absence of other concerns.

The bigger problem

Back in the general discussion, though, Dave Chinner argued that the focus on negative dentries was addressing a symptom of the problem and missing the bigger issue. The real problem, he said, is that memory pressure is the only mechanism the kernel has for controlling the size of the many caches it maintains:

Yup, the underlying issue here is that memory reclaim does nothing to manage long term build-up of single use cached objects when *there is no memory pressure*. There's [plenty] of idle time and spare resources to manage caches sanely, but we don't. e.g. there is no periodic rotation of caches that could lead to detection and reclaim of single use objects (say over a period of minutes) and hence prevent them from filling up all of memory unnecessarily and creating transient memory reclaim and allocation latency spikes when memory finally fills up.

Rather than worry about the dentry cache, he said, developers should come up with a mechanism that can manage the size of all in-kernel caches. Wilcox agreed in principle, but cautioned against making the problem so broad that it becomes intractable. Chinner doubled down, though, saying that multiple kernel caches have the same problem, and that a solution for one, based on some sort of periodic scanning to age items out of the cache, would be instantly applicable to all of them.

This discussion has mostly wound down without any suggestion that anybody is setting out to create the more general cache-aging mechanism that Chinner would like to see. The problem remains, though, and seems unlikely to go away by itself. So the chances of this discussion showing up in an LSFMM slot seem fairly high. Perhaps an in-person discussion — the first in the memory-management and filesystem communites in three years — will lead to some sort of consensus on a solution, preferably one that will be implemented before another 20 years pass.

Comments (34 posted)

Readahead: the documentation I wanted to read

The readahead code in the Linux kernel is nominally responsible for reading data that has not yet been explicitly requested from storage, with the idea that it might be needed soon. The code is stable, functional, widely used, and uncontroversial, so it is reasonable to expect the code to be of high quality, and largely this is true. Recently, I found the need to document this code, which naturally shone a rather different light on it. This work revealed minor problems with functionality and significant problems with naming.

My particular reason for wanting documentation probably colors my view of the code so I'll start there. Once upon a time, Linux had a strong concept of "congestion" as it applied to I/O paths. If the queue of requests to some device grew too large, the backing device would be marked as "congested" and certain optional I/O requests would be skipped or delayed, particularly writeback and readahead. As time has passed, so too (apparently) has the need for congestion management. Maybe this is because many I/O devices are now faster than our CPUs but, whatever the reason, the block layer no longer tracks congestion and only a few virtual "backing devices" continue this outdated practice.

In Linux 5.16, the only backing device that gets marked as "read congested" is the virtual device used for FUSE filesystems. As part of a project to remove all remnants of congestion tracking, I proposed that there was really nothing special about FUSE, and it should just accept all readahead requests just like everyone else. Miklos Szeredi, the maintainer of FUSE, found my reasoning to be unsatisfactory — and who could blame him? If FUSE doesn't want readahead requests, it shouldn't have to accept them. Trying to understand how FUSE could safely say "no" to readahead, without having to maintain the congestion-tracking functionality in common code, started me on the path to understanding readahead — once it was explained to me that it wasn't as simple as just changing the "readahead" callback in FUSE to return zero.

The main part of the API exported by mm/readahead.c is two functions: page_cache_sync_ra() and page_cache_async_ra(). This functionality is also available with a slightly simpler interface as page_cache_sync_readahead() and page_cache_async_readahead(), which are nicely documented in the kernel documentation.

Sync and async

Unfortunately, that documentation is not explicit on how the "sync" or "async" in the names are relevant. Clarifying this was among my first tasks so, to help with that clarification, I'll refer you to a selection from my new documentation, which was merged for the 5.18 release. It starts:

Readahead is used to read content into the page cache before it is explicitly requested by the application. Readahead only ever attempts to read pages that are not yet in the page cache. If a page is present but not up-to-date, readahead will not try to read it. In that case a simple ->readpage() will be requested.

Readahead is triggered when an application read request (whether a system call or a page fault) finds that the requested page is not in the page cache, or that it is in the page cache and has the PG_readahead flag set. This flag indicates that the page was loaded as part of a previous readahead request and now that it has been accessed, it is time for the next read-ahead.

Each readahead request is partly synchronous read, and partly async readahead.

We stop here, in mid-paragraph, to focus on those two terms: sync and async. Readahead is, by its nature, asynchronous — nothing is waiting for it. An explicitly requested read, instead, will ultimately be synchronous, as the operation cannot complete until the data arrives. These two modes are clearly related and handling them both in the same code makes sense. Describing them both as being "readahead" — a choice that was effectively forced on me by the code — is not so defensible.

Anyone who has been around computers long enough to know that a "kilobyte" isn't (necessarily) 1000 bytes will also know that we technologists often follow the practice of Lewis Carroll's "Humpty Dumpty" in Through the Looking Glass:

"When I use a word," Humpty Dumpty said in rather a scornful tone, "it means just what I choose it to mean — neither more nor less."

We seem to make that mistake rather more than is good for us, and the readahead code is certainly not innocent.

Each filesystem can provide an address_space_operations method, named readahead(), to initiate a read; it is on this basis that the term "readahead request" is used in the documentation. There is also an address-space operation called readpages(), though it was marked as deprecated in the middle of 2020 and will be removed for 5.18. These two functions have much the same functionality (they both issue read requests for a collection of pages). The newer readahead() has a much better interface (the details are beyond the scope of this article), but readpages() has undoubtedly the better name — because that is what they both do. They don't just "read ahead" but also issue reads that have explicitly been requested.

Once one realizes that the functionality of readahead() is just to submit read requests, some of which the caller will wait for ("sync") and some of which the caller won't wait for ("async"), the intention of the code starts to become a lot clearer. Names matter.

When readahead can be skipped

Returning to the original problem of giving FUSE the opportunity to skip readahead, a way forward now appears. The readahead() function that FUSE supplies must read all the pages that will be waited for, but it doesn't need to read the remainder. One of the improvements to the interface that came with the introduction of the readahead() operation is that more information is available to the filesystem. This information includes a struct file_ra_state, which contains a field called async_size. Aha! This must be the size of the readahead section.

Or is it? Can we trust the name? This structure is, fortunately, documented; the description for this async_size field reads: "Start next readahead when this many pages are left". What does that mean, and what does it have to do with being "async"? Possibly reading some more of the new documentation will help.

Each readahead request is partly synchronous read, and partly async readahead. This is reflected in the struct file_ra_state which contains ->size being to total number of pages, and ->async_size which is the number of pages in the async section. The first page in this async section will have PG_readahead set as a trigger for a subsequent readahead. Once a series of sequential reads has been established, there should be no need for a synchronous component and all readahead requests will be fully asynchronous.

The second sentence, which presents the meaning of async_size, is something I made up — it was not previously present in any documentation and is not completely consistent with the code, though it matches the field name perfectly. The third sentence, about the PG_readahead flag, matches the code and pre-existing documentation.

A core idea in readahead is to take a risk and read more than was requested. If that risk brings rewards and the extra data is accessed, then that justifies a further risk of reading even more data that hasn't been requested. When performing a single sequential read through a file, the details of past behavior can easily be stored in the struct file_ra_state. However if an application reads from two, three, or more, sections of the file and interleaves these sequential reads, then file_ra_state cannot keep track of all that state. Instead we rely on the content already in the page cache. Specifically we have a flag, PG_readahead, which can be set on a page. That name should be read in the past tense: the page was read ahead. A risk was taken when reading that page so, if it pays off and the page is accessed, then that is justification for taking another risk and reading some more.

Which page should this flag be set on? Another core premise of readahead is that reads are often sequential, and it is only on this basis that we take a risk and read the following pages. So if the first of the ahead-read pages is accessed, then a sequential read can be assumed. If some later page is read, less can be concluded. It seems clear to me that PG_readahead must be set on the first of the pages that were opportunistically requested. This is consistent with the documented behavior of setting it based on the value of async_size, and is consistent with most of the code, though there are a couple of places where some different value is used with no clear justification.

This, then, is enough to allow FUSE to choose when to skip pages in its readahead() handler — it looks at the async_size value — but it isn't quite enough for completely correct behavior. When readahead() is called, the pages of memory have already been added to the page cache, though they have not yet been marked up-to-date. Leaving them there without initiating a read can result in later attempts to read them being less efficient. This can easily be fixed by having the caller drop pages from the page cache if the readahead() function chose to ignore them and indicated this by not updating some (private) fields in struct readahead_control.

Oddities

There is a bit more to the documentation, and there are more oddities that only came to light because of the need to document. So, picking up where we left off:

When either of the triggers causes a readahead, three numbers need to be determined: the start of the region, the size of the region, and the size of the async tail.

The start of the region is simply the first page address at or after the accessed address, which is not currently populated in the page cache. This is found with a simple search in the page cache.

The size of the async tail is determined by subtracting the size that was explicitly requested from the determined request size, unless this would be less than zero — then zero is used. NOTE THIS CALCULATION IS WRONG WHEN THE START OF THE REGION IS NOT THE ACCESSED PAGE.

Often I have used the act of documentation as a means for finding and fixing bugs — if accurate documentation starts to look contorted, it can be easier to fix the code first so as to allow the documentation to be more coherent. In this case I chose to leave the document clumsy, in part because naming was again a problem, and as we know, finding good names is hard.

As mentioned, the readahead code has two API functions with unfortunate names: page_cache_sync_ra() and page_cache_async_ra(). These are called in response to the two triggers — when trying to access a page that is not cached, or when accessing a page that was flagged as PG_readahead. Both might issue reads that will soon be waited on (sync) as well as reads that might not be (async).

Each of these functions has a final argument called req_count, which is the count of pages in the initial request. The implication is that we need at least that many pages, but it is OK to request more if that seems appropriate. It is the meaning and use of req_count that resulted in that loud NOTE ending that above section of documentation.

Interpreting req_count as "size of the initial request" matches the name, but it isn't always obvious that this is the number being passed in. As we have seen, the logic in the readahead code is mostly about guessing how much data might be needed in the future. Some callers of these functions already know that a sequential read is happening, for example because the madvise() system call has been used to declare the application's intentions. In these cases, req_count is set to a suitably large number. This isn't exactly the number of pages that are needed now, but it is the number of pages that are known to be wanted, so these are pages that the filesystem should not skip just because it is inconvenient to read them just now.

With the caveat that the request may include explicitly requested future pages, it is fairly clear what req_count means, but how is it used? Before diving in to explore this, it will help to read a bit more of the new documentation to understand how the size of a readahead request is calculated.

The size of the region is normally determined from the size of the previous readahead which loaded the preceding pages. This may be discovered from the struct file_ra_state for simple sequential reads, or from examining the state of the page cache when multiple sequential reads are interleaved. Specifically: where the readahead was triggered by the PG_readahead flag, the size of the previous readahead is assumed to be the number of pages from the triggering page to the start of the new readahead. In these cases, the size of the previous readahead is scaled, often doubled, for the new readahead, though see get_next_ra_size() for details.

For the page_cache_sync_ra() case, called when a wanted page is missing, one would expect req_count to be at least one, and that is in fact the case. Some number of pages will be allocated, depending how big a hole there is in the page cache, how big the request is, and how much readahead seems justified. These pages are added to the page cache and the filesystem's readahead() function is called to load them.

When page_cache_async_ra() is called because a PG_readahead flagged page was found, the situation is different. The set of pages that will be read will not include the page that was just found (it has already been read) and probably not some number of subsequent pages. The code will search through the page cache for the first missing page, and consider reading from there. How many of these pages will be among those needed for the initial request? Maybe some, certainly not req_count of them.

That last claim of the relationship between req_count and the pages actually read is based on assumptions which, as I have occasionally suggested, are not always completely consistent with the code. To be sure, we need to go back to the code and see how req_count is actually used in the page_cache_async_ra() case. Fortunately we have many years of development history in Git, and the documentation found for individual patches is often better than documentation found in the code.

req_count through the ages

Prior to Linux 2.6.31, req_count (then called req_size) wasn't used for the reads triggered by PG_readahead at all. The change in that release caused it to be used to increase the size of ahead reads. Previously, this was calculated as the size of the previous ahead read, scaled up by a factor of two or four. Since then, it is the size of the previous ahead read plus req_count, and then scaled up. The justification for this change was:

Make sure interleaved readahead size is larger than request size. This also makes the readahead window grow up more quickly.

Unfortunately, there is no indication of the sort of workload that would benefit from this change. To me, it has the appearance of req_count being used not because it was the right number based on some theoretical analysis, but because it was an easily available number that was about the right size. So this doesn't provide much insight into what req_count is supposed to mean.

Then, in Linux 4.10, req_count found a new use. That patch allowed the number of pages requested in the readahead process to be at least the size of the original request, even if that is larger that maximum readahead size that is configured (as long as it wasn't bigger than the device was configured to accept). This is a clear acknowledgment that part of the "readahead" is really a synchronous read, not to be constrained by readahead limits. It also emphasizes that req_count isn't simply a size (maybe to be used for scaling), but it identifies a specific set of pages — from the starting point of the request. So when the starting point for readahead is moved forward over any pages that are already in the page cache, the req_count really should be reduced by the number of pages skipped over. Only then will it still signify the number of pages that are part of the original request, which still need to be read and which can justify exceeding the maximum readahead size.

From a purely behavioral perspective, this lack of clarity over the meaning of this parameter may not be all that important. Readahead size calculations are heuristics. There is no right answer and, if a couple of extra fudge factors slip in by mistake, it is just a different heuristic. But from the perspective of wanting to understand the code, and particularly of wanting to change the code without breaking anything, this sort of detail can be quite important.

As mentioned, I want the filesystem to know how many pages were explicitly requested, and how many were heuristically suggested. This requires a clear understanding of what req_count means. Getting slightly incorrect data may not hurt a lot, but it certainly doesn't help.

The rest of the story

And now we can read the remainder of the documentation, which hopefully will integrate some of the ideas already explored. As it is aimed at people who are already generally familiar with the Linux page cache, it contains some concepts such as page locking that are best just skipped over by the casual reader.

If the size of the previous read cannot be determined, the number of preceding pages in the page cache is used to estimate the size of a previous read. This estimate could easily be misled by random reads being coincidentally adjacent, so it is ignored unless it is larger than the current request, and it is not scaled up, unless it is at the start of file.

In general, readahead is accelerated at the start of the file, as reads from there are often sequential. There are other minor adjustments to the readahead size in various special cases and these are best discovered by reading the code.

The above calculation, based on the previous readahead size, determines the size of the readahead operation, to which any requested read size may be added.

Readahead requests are sent to the filesystem using the ->readahead() address space operation, for which mpage_readahead() is a canonical implementation. ->readahead() should normally initiate reads on all pages, but may fail to read any or all pages without causing an I/O error. The page cache reading code will issue a ->readpage() request for any page which ->readahead() does not provide, and only an error from this will be final.

->readahead() will generally call readahead_page() repeatedly to get each page from those prepared for readahead. It may fail to read a page by:

• not calling readahead_page() sufficiently many times, effectively ignoring some pages, as might be appropriate if the path to storage is congested.

• failing to actually submit a read request for a given page, possibly due to insufficient resources, or

• getting an error during subsequent processing of a request.

In the last two cases, the page should be unlocked to indicate that the read attempt has failed. In the first case the page will be unlocked by the caller.

Those pages not in the final async_size of the request should be considered to be important and ->readahead() should not fail them due to congestion or temporary resource unavailability, but should wait for necessary resources (e.g. memory or indexing information) to become available. Pages in the final async_size may be considered less urgent and failure to read them is more acceptable. In this case it is best to use delete_from_page_cache() to remove the pages from the page cache as is automatically done for pages that were not fetched with readahead_page(). This will allow a subsequent synchronous readahead request to try them again. If they are left in the page cache, then they will be read individually using ->readpage().

The purpose of writing the documentation was to ensure that I understood the code and ensure that others would be able to understand my motivation for changes to that code. It has, I think, achieved that. However it has also opened up opportunities for making the code, and the names used in the code, more transparent. While I would like such improvements to happen, I'm not sure when I'll find time — through I would make time to help if someone else wanted to drive the effort.

The purpose of this meta-narrative about the writing of the documentation is different. I wanted to highlight the difficulty of maintaining a coherent "intent" or "meaning" of various details of the code, as it is modified by various people at various times. Meanings can drift, inconsistencies can accumulate, misnomers can become entrenched. As a community we have found that the best way to maximize correctness and consistency is to have tools that alert us to problems. Until we have tools that can read documentation (including the implicit documentation of variable names) and highlight inconsistencies, that is one part of the process that we will have to continue doing ourselves.

So please: when you change code, also change the documentation. And if there isn't any documentation yet — write some!

Comments (11 posted)