Leading items

Welcome to the LWN.net Weekly Edition for March 2, 2023

This edition contains the following feature content:

• Python packaging and its tools: the ongoing saga of how to improve packaging for the Python language, with a focus on which tool, if any, to standardize on.
• The first half of the 6.3 merge window: a summary of changes merged for the next kernel release — so far.
• Red-black trees for BPF programs: a new data structure for BPF programs provides a view into the sort of environment that the BPF developers are trying to create.
• Debian ponders filesystem-image forward compatibility: an e2fsprogs update creates problems for some users.
• Some useful tools for binary formats: a report from several FOSDEM talks on tools for working with binary data.

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)

Python packaging and its tools

The Python-packaging discussions continued in January and February; they show no sign of abating in March either. This time around, we look (again) at tools for packaging, including a brand new Rust-based entrant. There is also a proposal to have interested parties create Python Enhancement Proposals (PEPs) for packaging solutions that would be judged by a panel of PEP delegates in order to try to choose something that the whole community can rally around—without precluding the existence of other options. As always, it is all a difficult balancing act.

One tool

Picking up from where our last article left off, there was interest in finding a single tool that the Python Packaging Authority (PyPA) could push as the default. But Donald Stufft said that he is skeptical that the PyPA has the means to "bless a singular tool in a way that people will actually recognize it as 'the' tool". Beyond that, though, he is not sure that the clamored-for single, unified tool is even possible; everyone expects too much of such a tool.

I suspect that 100% of the users that want a unified tool, just blindly assumed that whatever their preferred workflow, or something like it, would of course be included in that tool, and they don't consider that they might have to make drastic changes to their workflow to get it-- but somebody is going to have to make drastic changes, because the reality is what exists now in the world are so varied that a singular tool can't possibly solve them all IMO.

Greg Roodt wondered if an enhanced pip might be the right path. Pradyun Gedam agreed, noting that pip already occupies the privileged/default position. Even though it is not sensible to "combine all the workflows/innovations into one thing", getting to a 90% solution is "not an intractable task", he said.

Paul Moore was concerned that adding these features to pip is not something that can be done quickly; "pip has a lot of technical debt which we would need to pay off before we could add a lot of extra complexity". Roodt acknowledged that, but, like Gedam, thought a few extra pieces would be sufficient to help simplify the ecosystem substantially. Stufft said that adding features to pip "is probably the least controversial way of arriving at a unified tool".

Both Moore and Stufft were worried about adding the virtual-environment management that is offered by other tools to pip, but they did discuss some possible approaches. Brett Cannon cautioned that, based on some investigation of virtual-environment workflows he had done recently, "there is no 90% answer, so there will be some teeth gnashing regardless of the decision".

Poetry creator Sébastien Eustace wondered if there was even a need for the PyPA to "endorse or promote a single tool". He noted that Poetry is an independent packaging tool that came about because of missing pieces in the PyPA tool set; it was never endorsed by the PyPA but still has become "the second most downloaded 'packaging' tool". Stufft said that the push for a single recommended tool arose because it is one of the most requested features from users; the current status quo works, but users are not happy with it. Any endorsement would simply set the default:

I don't think anyone is suggesting preventing there to be options. The question is whether there should be a recommended or "default" option, not whether we should provide an only option. Obviously users want it, and they don't feel well served by the status quo.

Ofek Lev was concerned about the "massive undertaking" required to add these extra features to pip; throughout, he has been advocating Hatch as a better candidate for the unified tool. Stufft's (and others') arguments boil down to a question of practicality, though; pip exists, it is used by a majority of Python users, is already recommended by the Python Package Index (PyPI), so it is the default default, so to speak. But Lev thinks that fundamentally changing pip will be difficult to do for a number of reasons:

Do we think the backends of Flit, Hatch, Poetry, PDM, etc. were created just for fun or because PEP 517 told us we could? No, it was because setuptools was too difficult to contribute to. And consider in that case that is merely improving upon its central and only purpose of building packages. In the case we're talking about here we're in a code base of equivalent size with even more complexity and we're talking about not just adding new features but fundamentally changing what it does/is.

It is probably not surprising that Stufft disagreed; he does not think it constitutes a fundamental change to pip, just further evolution of the tool:

In fact, pip can start adding those features today, without anyone's permission, and I suspect if they did so the "please provide a unified tool" talking point would just go away, because pip is already the default tool, it's just implementing the features that people keep asking for.

However, the ability of the pip maintainers to find the time to do that work is worrisome to various commenters. "H. Vetinari" said that it is "an intriguing idea to flesh out pip in this way", but there is a need to expand the maintainer group in order to "realistically grow all those features in something less than 'years'". Moore agreed that it would require some "fundamental changes to how pip is maintained" to speed up the development of these extra features. He had a long list of reasons that it would take a long time, including limited maintainer bandwidth and the preservation of legacy pip workflows.

But Moore also agreed that choosing pip neatly sidestepped the "which tool to bless" question; "I don't think we should underestimate the challenges", however. While users want a unified tool, they may not want to wait as long as it would take; "In 3-5 years? Maybe we could get pip to the point of being that tool in that sort of time period. In 6 months? Not a chance." Stufft said that users are mostly reasonable and will just want to see progress toward the goal; "I don't think there is a world where they get it in 6mos no matter what we do".

Ralf Gommers is skeptical about the pip-based plan. He said that "the weight of history, the complex and legacy code, the backlog of issues and difficulty of working on pip, and the important lower-level role as a pure installer it already fulfills are already stacked against this idea". He suggested that some combination of Poetry, Hatch, and PDM might be the right approach; "Each has its own problems and isn't complete enough, however if you'd take the best features of each you'd have about the right thing." Authors of each of those tools have commented in the thread, he said, so they could simply get together and produce a unified tool:

[...] I think it's safe to say that if these projects would join forces, we'd have something very promising and worth recommending as the workflow & Python project management tool. And it doesn't require a 200+ message thread with everyone involved in packaging agreeing - if a handful of authors would agree to do this and make it happen, we'd be good here and could "bless" it after the fact.

Gedam announced his (also lengthy) blog post that attempted to summarize his views and fill in lots of the background on the topic. He concluded that adding features to pip would be desirable, but that it is daunting. Developers interested in packaging have generally developed their own tools:

[...] we've made it fairly tractable to "build your own" in a sandbox that lets you ignore the need to support entire swaths of workflows, and that's something you can't compete with easily for contributor experience. And, when the alternative is "spend a few months trying to implement something in a 'legacy' codebase, while catering to needs that you don't have, also convince a bunch of people with limited availability that your idea is a good one and wait for them to review what you wrote", it's not surprising that we end up with a bunch of "new things" and have multiple groups building multiple workflow tools.

We still don't have agreement that this is the direction that we, as a community, want pip to go.

Battling PEPs?

Stufft was generally in agreement with Gedam's "excellent post", but he did take exception to the idea that the community is not in agreement. He believes that most users are in agreement that pip (or some other tool that is shipped with Python) should provide the "unified experience". Since pip is that tool, it should be enhanced, or some other tool should be shipped with Python, which would require agreement from the Python core developers by way of the steering council (SC). He proposed a kind of PEP "battle" to figure out which direction to go:

Interested parties write a PEP on how they think we should solve the "unification" problem within some time frame, all of these PEPs will have the same set of PEP-Delegates, the various proposals will be discussed just like any other PEP, then the PEP-Delegates will pick one and that's the direction we'll go in. [...] If they are unable to come to an agreement, then it will get kicked up to the SC to make a choice.

My recommendation is that we do something a little unorthodox and instead of having a singular PEP-Delegate, we instead have a team of 3 of them, who will together select the direction we go in. My rationale here is that this is our first time making a decision quite like this, it's going to be a decision with a large impact, and there is no one singular person who could make this decision who isn't biased in some way.

Christopher A. M. Gerlach (C.A.M. Gerlach), who is one of the PEP editors, further refined the idea and offered his assistance. There has been at least one volunteer for the PEP-Delegate group that would evaluate the PEPs, but, as of yet, there has been no visible action on the creation of PEPs to consider. It is not at all clear that those who might be in a position to propose a PEP and push it through to "completion" want to put in the enormous effort required to do so. Multiple competing visions seems like it may be even more of a stretch, but we shall see—it has only been a little over a month since Stufft suggested that path.

A new tool

On January 20, though, Nathaniel J. Smith announced a new tool (and binary format) that, to a certain extent, upends the usual order of things. He noted that one of the goals of Kushal Das, who was one of the authors of PEP 582 ("Python local packages directory") back in 2018, was that Python beginners only need to download a single thing in order to get started with the language. The PEP, which is still being discussed, was a means to that end. Smith looked at the problem from a different angle:

Historically, our tools have started with the assumption that you already have a Python, and now you want to manage it. That means every tool needs to be prepared to cope with every possible way of installing/managing Python. It means a beginner-friendly workflow tool has to be part of the interpreter (the main motivation for PEP 582), even with all the limitations that imposes [...]

But what if we went the other way, and uploaded CPython to PyPI, so you could pip install python? Well, OK, you couldn't actually pip install it because pip is written in Python, but pretend we had a tool that could do this. Then Kushal's beginners could install this one tool, and it could bootstrap Python + the packages they needed.

Pybi is Smith's format for packaging CPython binaries for distribution, which is similar in form to the wheel format used by PyPI. That way, some tool could download the latest Python, install it, and pre-populate the install with some packages of interest from PyPI. As noted, though, that tool would not have access to a Python environment, so Smith also developed posy in Rust. In part, posy is meant to be a way for Smith to exercise his Rust skills. The GitHub site README starts with an homage, calling the project: "Me messing around in Rust for fun (just a hobby, won't be big and serious like pip)". The eventual goal sounds fairly serious, however:

• A project-oriented Python workflow manager, designed to make it easy for beginners to write their first Python script or notebook, and then grow with you to developing complex standalone apps and libraries with many contributors.
• A combined replacement for pyenv, deadsnakes, tox, venv, pip, pip-compile/pipenv, and PEP 582, all in a single-file executable with zero system requirements (not even Python).

The reception to the announcement ranged from generally positive to something approaching "over the moon", though there are still plenty of reservations, of course. For the most part, posy simply implements the existing packaging standards, but it also takes into account the lifecycle model that was discussed at a 2018 core sprint. That model ranges from beginners (or, more broadly, simple projects, perhaps consisting of a handful of scripts) through deployable web applications, reusable libraries, and standalone applications; it has come up multiple times in these packaging discussions.

Gedam was concerned that posy is inventing yet another scheme for virtual-environment handling, among other things; he raised the inevitable specter from the xkcd: Standards comic. Moore agreed with some of those concerns, but was happy to see posy take the full lifecycle into account:

Most tools and approaches I've seen either frame themselves as "beginner friendly" (stage 1 and maybe 2), or as aimed at stage 3 (deployable webapp/reusable library/standalone app) and later. And both groups assume that stages 1 and 2 - "simple scripts" and "sharing with others" are beginner workflows, not needed by more advanced users [...] Or at least, that's how the documentation, examples and discussions feel to me.

I've no idea whether this project will succeed in unifying the full lifecycle described in that document. I don't know if it'll make our existing problems worse. I'm concerned about the fact that it's inventing new mechanisms for things like isolation that may or may not work. I suspect that a model based around heavy manipulation of sys.path will cause huge problems for the static typing community, for example. But I'm pleased that someone is looking at a problem which I feel like struggled to express well enough to get the existing tools to pay attention to [...], and I'm glad that we're still innovating, and not just fighting to consolidate what we have and deal with legacy issues.

While "some of the ideas here are interesting", Stufft said, there were some things that he was "not particularly enthused about", including an unclear deployment story, an unnecessary extra binary format, and the implementation language. "I personally enjoy Rust, but I think it speaks to a serious shortcoming in the idea that it relies on being written in an external language to make it viable." He argued that the only Rust property that was being employed was that it can create a standalone binary, which is really just a property of compiled languages; it could have "used one of the various strategies that exist to create a single file executable out of Python", instead. He is concerned that it gives the wrong impression:

The language choice is a short coming, because it has the implication that the packaging tool isn't capable enough to produce real world software that is meant to be deployed to end user machines, machines that you can't rely on the system Python on. After all, there's nothing inherently special about posy here, it's just an application that wants to run without the dependence of an existing Python install.

Smith pointed out that posy would not exist at all if it were not written in Rust, however, since that was part of why he wrote it. Stufft acknowledged that, but is concerned that by sidestepping (via Rust) the problem of delivering a Python command-line application to users, that important part of the overall Python-packaging story is being skipped as well. He clarified that point further in another post: "My assertion is that packaging things for distribution to end users is also part of the packaging story, because well it is, and it's one of the most chronically underserved parts of our packaging story [...]".

The thread continued on a ways and it appears there is a fair amount of enthusiasm for Smith's approach. Where that goes from here is hard to say, but there is still a plenty of work needed to get to the point where posy can fully fill the niche he envisions for it. It may well make sense to merge the pybi and wheel formats into a "wheel 2.0" or similar; there is talk of doing so, which might be an effort that is independent of posy's future.

A new thread

As January came to a close, the thread for part one of the packaging-strategy discussion wound down and was eventually closed. In early February, the thread for the second part of the strategy discussion was opened, though it seems that much of the energy has gone out of the conversation(s), as the new thread had a rather desultory tone. Moore wondered if the discussion time might be better spent elsewhere. He asked: "But are these strategy discussions likely to deliver anything better, or are they just taking energy and bandwidth away from the people working on making progress?" Part of the problem is that the PyPA is effectively simply an interest group, rather than a decision-making body:

Discussions like this tend mostly to demonstrate that there's no uniform view on direction among PyPA members (let alone among non-PyPA projects like conda and poetry). [...] There wasn't much consensus on the previous discussion, so does that mean we have no strategy? Or will someone propose a strategy, in which case without a change in PyPA governance, what difference will that make? (Even with a change in governance, I don't see anyone imposing a particular direction on packaging projects - there's too much history of independence for that to happen any time soon).

That led Gedam to start something of a meta-thread where he responded to the frustrations that had been voiced about the discussions; he sympathized with those feelings, but felt that progress was being made. Beyond that, despite people feeling a sense of urgency to immediately solve the packaging problems, it is going to take a while to get there. "We're not going to magically/quickly solve issues that are happening at a larger-than-ever scale and that have grown into their current shape over more than a decade!"

Steve Dower suggested that some kind of focused, in-person gathering might be a better way to get some kind of resolution, though other options are possible: "Less ideal is to have regularly scheduled meetings in amongst other distractions, and at the bottom end is to have an online-only, text-only, open-invite discussion without a specific goal (sound familiar? :) )". Gommers wondered if there were any plans for such a gathering, but Gedam said that there were not, at least yet.

There is still fruitful discussion going on in various threads in the Packaging category of the Python discussion forum. It is clear that none of these questions or problems is going to be resolved anytime soon, though progress is slowly being made in various areas, just as it has been over the past decade or more.

It is probably the right time to let things play out a ways before we check back in on this freewheeling Python-packaging conversation. It will be interesting to see what, if anything, concrete comes out of it. There is, already, the pypackaging-native site, which describes many of the problems, but are there PEPs in the works to solve some of them? While the discussion is somewhat fragmented—and a bit fractious at times—there is a lot of attention being drawn to the problems right now, which may help lead the community to a workable path for a solution (or, more likely, solutions). Stay tuned ...

Comments (27 posted)

The first half of the 6.3 merge window

As of this writing, 5,776 non-merge changesets have been pulled into the mainline kernel for the 6.3 release; that is a bit less than half of the work that was waiting in linux-next before the merge window opened. This merge window is thus well underway, but far from complete. Quite a bit of significant work has been pulled so far; read on to see what entered the kernel in the first half of the 6.3 merge window.

Changes merged to date include:

Architecture-specific

• A large set of old and unused Arm board files has been removed, reducing the size of the kernel tree by over 150,000 lines. This (6.0) commit describes the list of systems for which board files have been removed. Meanwhile, devicetree files have been added to support 46 new arm64 systems.
• The new virtconfig build target for arm64 systems creates a relatively lightweight configuration intended to be booted on virtual systems.
• AMD's "automatic IBRS" feature is now supported. This is a Spectre defense that restricts indirect-branch speculation with less of a performance cost than that imposed by retpolines.
• The m68k architecture has gained support for system-call filtering with seccomp().
• Arm scalable matrix extension 2 instructions are now supported.
• BPF trampolines are now fully supported on s390x and RISC-V RV64 systems.

Core kernel

• The list of enhancements to the kernel's embryonic support for the Rust language is relatively small this time, but that support is, according to Miguel Ojeda, "getting closer to a point where the first Rust modules can be upstreamed". These changes include the removal of a non-applicable part of the alloc crate, an implementation of the Arc type (which provides a reference-counted pointer), the ScopeGuard type (which runs some cleanup code when it goes out of scope), and the ForeignOwnable type, which facilitates moving pointers between Rust and C code.
• There is a new document covering the stability expectations for BPF kfuncs; it describes the current status in the ongoing discussion of how stable the BPF API should be.
• The cgroup.memory=nobpf command-line parameter disables memory accounting for BPF programs; see this merge message for a discussion of the motivation behind this feature.
• There is a new red-black tree data structure available to BPF programs. See this merge message for more information.
• The restartable sequences mechanism now exports a "per-memory-map concurrency ID" to processes. This ID can be thought of (and treated like) a CPU number, but the numbers are kept as close to zero as possible. Its purpose is to enable more efficient per-CPU data structures in applications that are only using a subset of the CPUs on a large system. This commit contains some more information.

Filesystems and block I/O

• The tmpfs filesystem now supports ID-mapped mounts.
• Erofs has gained support for per-CPU file-data decompression, leading to reduced data-access latency.
• The Btrfs block allocator will now segregate extents by their size, so that any given block group is limited to extents that are small (less than 128KB), medium (up to 8MB), or large. This evidently reduces fragmentation, especially in workloads where allocation size correlates with file lifetime — something that evidently actually happens. See this commit message for some details.
• Rotating disk drives still exist, and are even becoming more complex: multi-actuator drives have independently controllable arms that, for best performance, must all be kept busy. The BFQ I/O scheduler has gained support for such drives; this commit message has a bit more information on how it works.

Hardware support

• GPIO and pin control: Qualcomm QDU1000/QRU1000, IPQ5332, SA8775P, and SM8550 pin controllers, Mediatek MT7981 pin controllers, and StarFive JH7110 pin and GPIO controllers.
• Hardware monitoring: MPS MPQ7932 regulators, HPE GXP fan controllers, NXP MC34VR500 power-management ICs, and Infineon TDA38640 voltage regulators.
• Input: EVision keyboards and Steam Deck force feedback controllers.
• Miscellaneous: Xilinx ZynqMP on-chip-memory controllers, MediaTek low-voltage thermal sensor controllers, Intel topology aware register/pm capsule interfaces, Aspeed ACRY RSA engines, StarFive JH7110 random number generators, Maxim MAX20411 single step-down converters, and Broadcom BCMBCA HS SPI controllers.
• Networking: Microchip KSZ9563/LAN937x Ethernet switch PTP clocks, Realtek RTL8188EU wireless interfaces, Ocelot VSC7511, VSC7512, VSC7513 and VSC7514 external switches, Amlogic GXL-based MDIO bus multiplexers, Motorcomm 8531 PHYs, and Qualcomm WiFi 7 (ath12k) interfaces.
• Sound: MediaTek MT8188 controllers, Iron Device SMA1303 audio amplifiers, Renesas IDT821034 quad PCM codecs, Awinic AW88395 audio amplifiers, Realtek RT712 SDCA codecs, and Infineon PEB2466 quad PCM codecs.
• Also: preliminary support for writing human-interface device drivers in BPF has been merged, though the mechanism for distributing such drivers is still to be worked out. See this document for more information.

Networking

• Support for the Physical Layer Collision Avoidance (PLCA) Reconciliation Sublayer has been added; it is said to improve access performance on shared media Ethernet. This documentation patch describes how to configure and use this feature.
• The "wireless extensions" API for the control of WiFi interfaces ran into trouble in 2006, but is still supported as an emulation layer. This API will no longer be supported for WiFi 7 (802.11be) interfaces, since it is unable to configure all of the available features. The use of the wireless extensions API will generate a warning for most current devices as of 6.3.
• The process of documenting the netlink API continues; the results can be seen in the core API and user-space API manuals. Also added is a new tool to generate netlink protocol code from YAML specifications.
• The new IP_LOCAL_PORT_RANGE socket option makes it easier for multiple hosts to make outgoing connections through a NAT gateway; this commit contains details.
• Multi-path TCP can now handle mixed flows using both the IPv4 and IPv6 protocols.
• BIG TCP support has been extended to IPv4.
• The new default_rps_mask sysctl knob allows the creation of a default, per-net-namespace receive packet steering (RPS) configuration.
• Support for a number of queuing disciplines (specifically class-based queuing (CBQ), ATM virtual circuits (ATM), differentiated service marker (dsmark), traffic-control index (tcindex), and resource reservation protocol (RSVP)) has been removed due to a lack of maintenance and interest.

Internal kernel changes

• The old memory-allocation function get_kernel_pages() has been removed now that there are no more in-tree users.

The 6.3 merge window can be expected to remain open until March 5, at which point 6.3-rc1 will come out and the kernel will enter the stabilization phase of the development cycle. Quite a few more changes are poised to enter the mainline before that happens, though; tune in once the merge window closes for a summary of the rest of that work.

Comments (15 posted)

Red-black trees for BPF programs

Most of the kernel's code is written in C and intended to be run directly on the underlying hardware. That situation is changing in a few ways, though; one of those is the ability to write kernel code for the BPF virtual machine. The 6.3 kernel release will include a new API making the red-black tree data structure available to BPF programs. Beyond being an interesting feature in its own right, this new API shows how BPF is bringing a different approach to kernel programming — and to the C language in general.

The kernel has long made extensive use of red-black trees (rbtrees), which are a form of binary tree; this data structure offers fast lookups and the ability to perform insertions and deletions in bounded time. Red-black trees are found in I/O schedulers, graphics drivers, filesystems, the BPF verifier, CPU-scheduler run queues, network protocols, and beyond. One place they have not been found, though, is in programs written to run in the BPF virtual machine. As the complexity of BPF programs grows, though, so does the demand for advanced data structures. The BPF version of the red-black tree, added by Dave Marchevsky, is meant to address this need.

Within the kernel, data intended to be stored in an rbtree must be stored in a structure that embeds a struct rb_node. The BPF API looks similar in this respect; as described in the cover letter to the patch set, the first step is to define a structure to hold the data of interest along with a bpf_rb_node structure:

    struct node_data {
    	long key;
    	long data;
    	struct bpf_rb_node node;
    };

Kernel code will then declare a variable of type struct rb_root to hold the root of the tree. The interface for BPF programs looks a bit different; they must declare the root and associate it with the type it contains using a magic macro:

    struct bpf_rb_root tree_root __contains(node_data, node);

The program must also declare a spinlock and, by storing it into an array map alongside the tree_root variable, associate that lock with the red-black tree.

Thereafter, there are three functions (as of 6.3) that can be used to work with the rbtree:

    void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
    		   	bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b));
    struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,
			struct bpf_rb_node *node);
    struct bpf_rb_node *bpf_rbtree_first(struct bpf_rb_root *root);

Adding a node is done with bpf_rbtree_add(); the less() function is used to compare nodes so that the new node can be properly located within the tree. The first node in a tree can be had with bpf_rbtree_first(), and nodes can be removed with bpf_rbtree_remove(). It is a fairly bare API for now; more functions can be expected to appear in the future.

There are a number of interesting aspects to this API, starting with the fact that it exists at all. For a long time, there was only one way to add a complex data structure to BPF: as a BPF map. The BPF virtual machine simply did not have the support needed allow programs to directly manipulate data structures of any complexity. That has changed, especially with the addition of kfuncs (which allow BPF programs to directly call functions in the kernel), and better management of pointers. These features, along with the BPF verifier, create an environment that differs considerably from ordinary kernel development.

For example, as noted above, the program must associate a spinlock with the red-black tree. Once that is done, the verifier will ensure that no access to the tree — or to the data contained within it — happens unless the spinlock is held at the time. Acquiring a spinlock to access a data structure protected by that lock is mandatory in kernel code; severely unpleasant things will happen if the rule isn't followed. But the language itself cannot enforce that rule, so locking bugs are a fairly routine occurrence. As long as the verifier is doing its job properly, similar bugs cannot occur in BPF programs, at least as far as access to an rbtree is concerned.

The verifier also enforces rules regarding the ownership of pointers. For example, the first step in adding a node to an rbtree will be allocating that node, which is typically done with a call to bpf_obj_new(). On return from that call, the program will own the resulting pointer, and the verifier must be able to convince itself that the program will suitably dispose of that pointer before it exits. One way to do so is to free the memory again, naturally, but that is not hugely interesting. Another is to use bpf_rbtree_add() to add the new node to an rbtree, which will then take responsibility for it. If the program removes a node from the tree, it must, once again, take responsibility for disposing of it or the verifier will not let it run.

In other words, the verifier is implementing a sort of ownership model to ensure that memory leaks do not happen. It can also ensure that, once an object has been freed, the BPF program will no longer attempt to access it. In the case of rbtrees, implementing that check took some work, since accessing the tree (with bpf_rbtree_first(), for example) can create "non-owning" references that must all be invalidated when a node is freed. In other words, the verifier is preventing the creation of dangling pointers via aliases to a freed data structure.

The end result of all this checking is a programming environment that seems a bit more Rust-like and less C-like; there are whole classes of bugs that are eliminated before a program is allowed to run. Making the verifier happy can be a notoriously difficult task for some programming patterns, but the end result should be a higher level of assurance that the program will not damage the kernel.

Meanwhile, as of this writing, there are no users of the new data structure in the kernel. As a general rule, kernel developers will resist the addition of an API without associated users, but BPF is different; the whole point of a BPF API is to be available to programs that are not part of the kernel tree. There is one known user out of the kernel tree in the form of the extensible scheduler class; it would not be surprising to see others turn up as well.

As BPF maintainer Alexei Starovoitov said at a conference in 2022, the intent behind the BPF work is to create a safer version of the C language for kernel programming. This work is being done outside of the normal limelight that follows programming-language development and, like much of the kernel, is not following any sort of long-term roadmap. If this effort succeeds, kernel programming in the coming years may be quite different from how it has been until now. The addition of the red-black tree for BPF programs, in other words, is a piece of an interesting and novel forest.

Comments (8 posted)

Debian ponders filesystem-image forward compatibility

Developers who build distributions often (but not always) put considerable effort into backward compatibility, ensuring, for example, that a program built for one release will continue to run on later releases. Forward compatibility, where it is possible to move a program (or other artifact) from a more recent release to an older one, can be less of a concern, but it still tends to be seen as something that is better to not break if possible. So it is not surprising that an issue affecting the forward-compatibility of ext4 filesystems built for the upcoming Debian 12 ("bookworm") release has generated a fair amount of discussion, even if the number of affected users is likely to be small.

Some background

Filesystem implementations make a distinction between the data they store and the metadata that describes that data and the structure that holds it. While corruption anywhere in a filesystem is bad news, metadata corruption can be especially insidious, leading to loss of the entire filesystem, system crashes, widespread data corruption, and more. So filesystem developers go out of their way to be able to both detect and recover from metadata corruption.

One frequently used technique toward this goal is metadata checksumming, which will, at a minimum, make it possible to notice when a filesystem's metadata has been corrupted. For ext4, metadata checksumming was first added by Darrick Wong for the 3.5 kernel release in 2012. This feature worked well, but suffered from one little shortcoming: the UUID of the filesystem is included in the checksums. As a result, if an administrator wants to change a filesystem's UUID, all of the filesystem's metadata checksums must be recalculated and rewritten.

That is, needless to say, a slow operation. One might be tempted to think it would also be a rare operation, but that is not always the case. Specifically, use cases involving virtualization or containers often start by making a copy of a disk image, then giving that copy a unique UUID to ensure that the right copy is mounted inside each virtual system. Having to rewrite that filesystem's metadata slows the whole process of launching a new machine.

To address this problem, Wong modified the checksum mechanism for the 4.4 kernel in 2015. If the new metadata_csum_seed option is selected, then the seed value used for checksums will be stored in the filesystem superblock rather than calculated from the filesystem UUID at mount time. As a result, the UUID can be changed independently of the checksum seed, eliminating the need to rewrite all of that metadata.

The one little problem with this change is that it breaks compatibility with older ext4 implementations; they will not know to obtain the checksum seed from the superblock and will, as a result, miscalculate checksums. Such a filesystem implementation will quickly conclude that all of the filesystem's metadata is corrupted, leading to elevated blood-pressure problems in the user community. To avoid this confusion, metadata_csum_seed is marked as an incompatible feature in the filesystem superblock; any implementation that sees this feature bit set will realize that it is unable to understand the filesystem image and will refuse to mount it.

metadata_csum_seed comes to Debian

The e2fsprogs package contains utilities for working with ext4 filesystems, including fsck.ext4, mkfs.ext4, and quite a few others. The e2fsprogs v1.47 release, which happened on February 5, was the first in which mkfs.ext4 would create filesystems using the metadata_csum_seed option by default, more than seven years after support for that option was added to the mainline kernel. This version of e2fsprogs quickly found its way into Debian's unstable ("sid") repository, no doubt helped by the fact that the e2fsprogs maintainer (Ted Ts'o) is also the developer responsible for Debian's e2fsprogs package.

By February 8, the first bug report turned up. It seems that the GRUB bootloader, which has to be able to read filesystem images, never gained support for ext4 filesystems using metadata_csum_seed; as a result, filesystems created with the new e2fsprogs could not be booted from. This should not have been entirely surprising, given that a bug noting this incompatibility had been filed in 2017. A fix for GRUB evidently only made it into that project's repository in June 2021, but there has been no GRUB release since then, so released versions of GRUB still cannot handle this feature. The version of GRUB packaged for Debian was quickly patched and uploaded to sid, and the problem seemed solved.

Except that, as Daniel Leidert noted in a separate bug report, that is not entirely true. The new e2fsprogs remains incompatible with any previous releases of Debian, including derivatives:

Grub in Bullseye or any current Ubuntu release *cannot* deal with a filesystem created by this version of e2fsprogs. This basically breaks the debootstrap method of installing a Debian or Ubuntu. If e2fsprogs 1.47.0 is allowed into Testing, we can no longer use the debootstrap method to install a Debian Bullseye (or older) or any Ubuntu release.

Leidert saw this change as a break in forward compatibility, and one that should not be allowed to proceed into the bookworm release, especially since the change is recent and there has been little time to prepare for it. He went as far as claiming that the change is a violation of the Debian Social Contract, specifically the provision saying that the project prioritizes its users.

Discussion

This is Debian, so opinions were not in short supply. Adrian Bunk suggested that the change breaks longstanding practice in Debian:

A rule of thumb is that any combination/mix of packages permitted by the package manager from two adjacent Debian releases should work whenever reasonably possible, since this reduces problems for our users during an upgrade, when using backports, or when temporarily going back to the version of a package from the previous stable due to a regression.

Former project leader Sam Hartman questioned whether Debian really wants to commit to that kind of stability. That said, he acknowledged that the change had come late in the release cycle and suggested that "a more orderly process" might involve deferring the change until after the bookworm release.

Ts'o, instead, compared this problem to that of building a program against a current version of the C library and expecting the resulting binary it to work on older releases — something that the project does not promise will work. There are a number of workarounds for users running into the ext4 problem, he said, including changing the default in /etc/mke2fs.conf, by supplying a command-line option when creating the filesystem, or even by turning metadata_csum_seed off after the fact with tune2fs.

He later highlighted that seven years had passed between the feature becoming available and being turned on by default, saying that "file system developers do understand the concern of needing to wait before enabling a feature by default". As an alternative to reverting the change, he proposed a documentation addition describing the problem, along with its workarounds, and making a point that he repeated a number of times in the discussion: "just as running and installing grub needs to be done in a chroot, it is best practice to run the mkfs command in a chroot as well". By running the version of mkfs shipped with the distribution release of interest, users can avoid this kind of incompatibility entirely.

While he remains clearly opposed to reverting the e2fsprogs change, Tso has also repeatedly said that, if the Debian release team requires that the default be changed, he will comply — albeit with the intent of reintroducing the change after the bookworm release. "I accept that this is the Release Team's call," he said, and asked for the decision to be made so that he could proceed accordingly.

Arguably the biggest problem here is simply the amount of surprise involved. As Russ Allbery observed, using mkfs to create filesystems for older distribution releases has worked for a long time, so nobody expects it to break now. If the change is not to be reverted he said, improved documentation to raise awareness of this particular pitfall will be needed. He also suggested the addition of a compatibility flag for mkfs that would set options appropriately for older releases. Ts'o, though, replied that just setting options might not always be enough to guarantee success.

On February 22, Paul Gevers announced the release team's position on this change:

I would like to affirm your position as a maintainer of e2fsprogs to make this kind of changes in your package and that's up to image builders to cope with that. However, because of the *timing* of the change we ask you to revert the change of the default settings for bookworm and please enable them once trixie opens.

So this issue would appear to be resolved for now. But, despite Ts'o's characterization of this discussion as "a tempest in a teacup", there is a more significant question to be answered here: what is the forward-compatibility guarantee, if any, that Debian provides to its users? If the end result of this discussion is a better understanding of the answer to that question, it will have been worth the tempest.

Comments (32 posted)

Some useful tools for binary formats

Linux users often work with text files; tools like grep, awk, and sed are standard utilities in their toolbox. However, these tools fall short when trying to extract or edit data from files in a binary format, analyze corrupt media files, or for parsing a binary data format. FOSDEM 2023 in Brussels had a whole binary tools devroom dedicated to open-source programs that deal with binary data.

Line-based text files can be handled with the standard tools, but even better tools exist for data formats that store structured data in text, like JSON, YAML, and XML. For JSON, the command-line processor jq has become popular. It was also the inspiration for at least two tools called yq that handle YAML, JSON, XML, and other text-based formats: one by Mike Farah and another by Andrey Kislyuk.

fq, or jq for binary formats

At FOSDEM, Mattias Wadman spoke about his tool fq, which he calls "jq for binary formats". He developed it because he works with media files a lot in his job and wanted to have a command-line tool to help with debugging broken media files, looking for unusual values or data structures, or just to automate data-extraction tasks over multiple media files.

Wadman explained that he liked jq a lot because of its CLI-friendly syntax to query, display, and transform JSON data. The syntax is terse and composable, it's easy to iterate and recurse over elements in a data structure, and it has powerful means to select and transform data. He wanted the same possibilities for data in a binary format, so he wrote fq. It is written in Go, and based on a Go implementation of jq. Both projects are MIT-licensed.

Fq has an expressive syntax. In its simplest forms, fq d file recursively shows a tree of decoded data structures, but it truncates long arrays; with fq dd file all bytes are shown. With fq . file only the upper level of the tree is shown. It's also possible to select for values fulfilling some condition, extract specific parts of the file's data structures, or compute histograms of values.

This way fq can be used for quick data-manipulation tasks on the command line, also as part of a shell script. It can also be started as an interactive read-eval-print loop (REPL) shell, using fq -i . file. This has autocompletion to easily discover structures in the file and navigate through the tree of structures. Another way to use fq is as a script interpreter. When regularly using the same fq command, one can create a script like:

    #!/usr/bin/env fq -d mp3 -rf
    [.frames[].header | .sample_count / .sample_rate] | add

This example computes the duration of an MP3 file by selecting the header of all frames, for each of these headers dividing the number of samples in the frame by its sample rate, and then adding all those results. In the same way, files in many other formats can be handled. The project also has some documentation about implementing a decoder for a new format.

Kaitai Struct

While fq is a useful command-line tool, Kaitai Struct focuses more on creating parsers for binary structures in a declarative and language-neutral way. Petr Pučil, a developer and maintainer of Kaitai Struct, talked about how he discovered the project. He wanted to create a Musical Instrument Digital Interface (MIDI) editor and, as part of this, he started writing a parser for SoundFont 2 (.sf2) files. "This was hard, and no fun", Pučil admitted. But when he found Kaitai Struct, it allowed him to do in one day what had taken him two months before.

So what is Kaitai Struct? Fundamentally, it's a declarative language that is used to describe arbitrary binary data structures. A data format is described in a .ksy file, using the YAML format. This is particularly interesting, because it can be used as a formal specification for the format. At the time of this writing, Kaitai Struct's format gallery has 181 specifications, including the ZIP archive format, the GPT partition table, the Executable and Linkable Format (ELF) for executable files, and the Audio Video Interleave (AVI) multimedia container format.

On top of that, Kaitai Struct is also a parser generator. When Mikhail Yakshin released its first source code in 2016, Kaitai Struct was able to compile the .ksy files into Java and Ruby code to parse the structures. By 2017, the project already supported 8 languages, and at this writing it is able to create parsers in 11 languages: C++/STL, C#, Go, Java, JavaScript, Lua, Nim, Perl, PHP, Python, and Ruby. In his talk, Pučil announced that Rust, C, and Julia parser generators are planned.

"It's really a write once, use everywhere approach", Pučil explained. Once a binary format is described in a .ksy file, Kaitai Struct's compiler is able to generate source code for parsers in these 11 programming languages. The compiler, ksc, is released under the GPLv3 license, but the run-time libraries for the generated code use the MIT or Apache-2.0 license. Thus generated code can even be used in proprietary applications.

Ksc has an interesting feature: one of its targets is not a programming language, but Graphviz's dot language. The resulting .dot file can be converted with Graphviz to a diagram showing the data structures defined in the .ksy file. This is an easy way to visualize a binary data format, perhaps as part of its documentation, for example.

Kaitai Struct comes with a couple of other utilities. With the ksv command, files can be parsed using a .ksy file, with their structure and the raw data visualized side by side. The user can open and close parts of the tree structure to interactively explore the data. Another command that comes with the ksv package is ksdump. This also visualizes the tree structure, but non-interactively: it just dumps the parsed structure for the given data in YAML, JSON, or XML format to the terminal.

Another tool that comes in handy while developing a .ksy file is the Kaitai Web IDE. This is an online editor and visualizer that shows the raw data and the parsed object tree for a .ksy file while editing it. This immediate feedback can speed up developing a format specification. The Web IDE has the GPLv3 license and can also be run locally.

Pučil ended his talk with a recent development: the Kaitai Struct team has been working for six months on serialization support. Serialization is the opposite of parsing: while parsing creates a structure from binary data (so it reads binary data), serialization converts a structure to binary data (so it writes binary data). The work on serialization has been financially supported by the NLnet Foundation. Currently, Kaitai Struct has a serialization generator for Java working and, according to Pučil, Python and C# implementations will be ready in two months.

With serialization, Kaitai Struct can be used to edit existing files in a binary format, to create new files from a structure, or even to convert a file between different formats. However, the current scope of the serialization implementation is rather narrow. The user must set everything in the data structure explicitly, including lengths, offsets, and magic numbers. Kaitai Struct only checks the consistency of the serialized data. Another limitation is that once a stream of data is created for serialization, it’s not possible to resize it later.

GNU poke

The GNU poke project had two talks in FOSDEM's binary tools devroom. José E. Marchesi gave an introduction to the tool and a status update of the project. GNU poke is an interactive, extensible editor for structured binary data from the command line. In contrast to a simple hex editor, GNU poke not only lets the user edit the data as a raw stream of bytes, but also in a structured way. Marchesi called GNU poke especially useful for reverse engineering and prototyping.

Of course, the poke program needs to know the data format the user is working with, and that's why the program comes with almost 50 "pickles". These are scripts in the Poke language that can read and write specific binary formats. Some pickles are even complex enough that they are distributed in their own packages, such as poke-elf to edit ELF object files, executables, shared libraries, and core dumps.

Users can also write their own pickles to edit files in other binary formats. The Poke language is statically typed and garbage-collected. A pickle includes the definitions of types, variables, and functions needed to parse and serialize the data format. So, by writing a custom pickle and loading it into GNU poke, users can create their own custom binary data editor.

The basic functionality of GNU poke is implemented in a C library, libpoke, which allows its features to be integrated into other tools. Marchesi demonstrated an example of this, where libpoke was integrated into GDB. "With GDB good at debugging and GNU poke good at poking at data, combining the two results in a tool that excels at both tasks", Marchesi concluded.

Apart from GNU poke's home page, there are two other web sites to learn more about the tool: Pokology is a community-driven web site maintained by poke users and developers, and Applied Pokology is Marchesi's blog about GNU poke.

GNU poke contributor Mohammad-Reza Nabipoor spoke about alternative user interfaces for the tool. In the recent GNU poke 3.0 release, Nabipoor contributed the poke daemon, poked. It links with libpoke and exposes its functionality to other programs over Unix sockets. This way, multiple clients can interact with poked simultaneously.

Nabipoor, who uses GNU poke to manipulate Bluetooth formats, built upon poked to create pacme, which he calls "an acme-inspired GNU poke interface". The acme he refers to is Rob Pike's text editor from the distributed operating system Plan 9 from Bell Labs.

Pacme consists of a bunch of small C programs, called pokelets, that interact with poked. They execute Poke code, process the results, and implement several components of the user interface, such as the REPL, byte dumps, a tree viewer, and an editor of Poke data structures. For its user interface, pacme is using the terminal multiplexer tmux with the various pokelets shown each in their own pane. There are some pre-defined layouts, or the user can open tmux panes and arrange them manually, and then open the pokelets in them for a custom interface.

Binary toolkit

All in all, having these tools could come in handy when working with various binary data formats. For extracting and filtering data on the command line, fq offers an accessible way. To edit binary data, GNU poke is a powerful tool. To parse and maybe serialize binary data in one of the supported programming languages, Kaitai Struct offers a flexible approach.

While these three tools have their own use cases, it's a little unfortunate that each has its own format library. There's a lot of overlap between the formats so there is a fair amount of duplicated work. Kaitai Struct is actively collaborating with the Construct Python data parser and builder project, however, and there are ideas flowing in both directions. The Kaitai Struct compiler has Construct as one of its targets, which allows converting a .ksy file to a Python file describing the same data format using Construct's declarative language. More of this type of collaboration between various projects in the space of binary data formats would be fruitful.

Comments (10 posted)