September 27, 2016 - Shuah Khan

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:

uvc_device

An example of embedded data structures.

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.

uvc_device_free

Use-after-free errors when the application exits

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.

  • 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.
fix_1

Dynamically allocated (de-embed) media_devnode

fix_2

cdev and media_devnode lifetimes should be linked.

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.

Shuah Khan

About Shuah Khan

Shuah Khan is a Senior Linux Kernel Developer at Samsung's Open Source Group. She is a Linux Kernel Maintainer and Contributor who focuses on Linux Media Core and Power Management. She maintains Kernel Selftest framework. She has contributed to IOMMU, and DMA areas. In addition, she is helping with stable release kernel testing. She authored Linux Kernel Testing and Debugging paper published on the Linux Journal and writes Linux Journal kernel news articles. She has presented at several Linux conferences and Linux Kernel Developer Keynote Panels. She served on the Linux Foundation Technical Advisory Board. Prior to joining Samsung, she worked as a kernel and software developer at HP and Lucent.

Image Credits: OSDC

Development / Linux drivers / embedded structures / lifetime management /

Leave a Reply

Your email address will not be published. Required fields are marked *

Comments Protected by WP-SpamShield Anti-Spam