Embedded Data Structures and Lifetime Management in the Linux Kernel

Embedded data structures are a common occurrence in Linux Kernel code. Use-after-free errors can easily creep in when they include multiple ref-counted objects with different lifetimes if the data structure is released prematurely. This article will explore some of the problems commonly encountered with lifetime management of embedded data structures when writing Kernel code, and it will cover some essential steps you can follow to prevent these issues from creeping into your own code.

What Makes Embedded Structure Lifetime so Complicated?

Let’s look at  a few examples of embedded structures. Structure A embeds structure B, structure B embeds structure C, and structure C embeds structures D and E. There is no problem as long as all these structures have identical lifespans and the structure memory can be released all at once. If structure D has a different lifespan overall or in some scenarios, then when structure A goes away, structure D goes along with it; any subsequent accesses to structure D will result in use-after-free errors.

Now for a real example from the Linux Kernel code:

struct uvc_device {
        struct media_device mdev;
        ........
}

struct media_device {
        struct media_devnode devnode;
        .......
}

struct media_devnode {
        struct device dev;
        struct cdev cdev;
        .......
}

struct device {
       struct kobject kobj;
       ........
}

Embedded Data Structures and Lifetime Management in the Linux Kernel - uvc_device

Memory backing struct uvc_device should not be released until the last user of struct device releases it. If uvc_device is released while struct device is still in use, any subsequent access to struct device will result in use-after-free errors.

Let’s look at some lifespan scenarios. The driver is unbound when no application is using /dev/media, and it then handles cleanup and releases the uvc_device resource and its embedded resources. There’s no problem in this case with the lifespans being identical. The same is applicable to when a device is physically removed or a driver module is removed via the rmmod command.

What happens when the driver is unbound or the device is removed when an application is actively using /dev/media and running syscalls and ioctls?

  • media_devnode->device is in use until the application closes the device file
  • media_devnode→cdev is in use until the application exits

The driver handles cleanup and releases the uvc_device resource and its embedded resources. Then, the application closes /dev/media and exits after the driver is gone; it will run into use-after-free errors on the freed resources: media_devnode->device and media_devnode->cdev.

Embedded Data Structures and Lifetime Management in the Linux Kernel - uvc_device_free

Please note, removing the driver module is not allowed because rmmod simply fails when the device (/dev/media) is in use.

How to Prevent Use-After-Free Errors in Your Code

What is the root cause?

  • Resources with different lifespan requirements embedded in the parent resource. Resources that are in use get released prematurely.

What’s the fix?

  • Dynamically allocate the resource(s) with different lifespans
  • Ensure the resource that embeds cdev doesn’t get released before cdev_del()
  • Dynamically allocate media_devnode to delink media_devnode lifetime from media_device. This will ensure that the media_devnode will not be freed when driver does its cleanup and frees uvc_device along with media_device
  • Set devnode struct device kobj as the cdev parent kobject linking media_devnode->device lifespan to cdev lifespan.
media_devnode->cdev.kobj.parent = &media_devnode->dev.kobj;
  • cdev_add() gets a reference to dev.kobj
  • cdev_del() releases the reference to dev.kobj ensuring that the devnode is not released as long as the application has the device file open.
Embedded Data Structures and Lifetime Management in the Linux Kernel - fix_1
Dynamically allocated (de-embed) media_devnode

Embedded Data Structures and Lifetime Management in the Linux Kernel - fix_2-1

It’s crucial to proactively test for corner cases and write a test to reproduce these problems. Please find the test procedure to reproduce and fix this problem in Linux 4.8 release under tools/testing/selftests/media_tests

It is always easier to avoid this design problem during development rather than finding and fixing it later. Pay attention to resources lifespan requirements and don’t embed resources with different lifespan requirements. Finally, make sure to follow up with proactive tests of resource lifetimes.

Author: Shuah Khan

Shuah contributes to multiple aspects of the Linux Kernel, and she maintains the Kernel Selftest framework.