Permalink
Fetching contributors…
Cannot retrieve contributors at this time
624 lines (460 sloc) 25.2 KB

-*- org -*-

Contiguous Memory Allocator

The Contiguous Memory Allocator (CMA) is a framework, which allows setting up a machine-specific configuration for physically-contiguous memory management. Memory for devices is then allocated according to that configuration.

The main role of the framework is not to allocate memory, but to parse and manage memory configurations, as well as to act as an in-between between device drivers and pluggable allocators. It is thus not tied to any memory allocation method or strategy.

Why is it needed?

Various devices on embedded systems have no scatter-getter and/or IO map support and as such require contiguous blocks of memory to operate. They include devices such as cameras, hardware video decoders and encoders, etc.

Such devices often require big memory buffers (a full HD frame is, for instance, more then 2 mega pixels large, i.e. more than 6 MB of memory), which makes mechanisms such as kmalloc() ineffective.

Some embedded devices impose additional requirements on the buffers, e.g. they can operate only on buffers allocated in particular location/memory bank (if system has more than one memory bank) or buffers aligned to a particular memory boundary.

Development of embedded devices have seen a big rise recently (especially in the V4L area) and many such drivers include their own memory allocation code. Most of them use bootmem-based methods. CMA framework is an attempt to unify contiguous memory allocation mechanisms and provide a simple API for device drivers, while staying as customisable and modular as possible.

Design

The main design goal for the CMA was to provide a customisable and modular framework, which could be configured to suit the needs of individual systems. Configuration specifies a list of memory regions, which then are assigned to devices. Memory regions can be shared among many device drivers or assigned exclusively to one. This has been achieved in the following ways:

  1. The core of the CMA does not handle allocation of memory and management of free space. Dedicated allocators are used for that purpose.

    This way, if the provided solution does not match demands imposed on a given system, one can develop a new algorithm and easily plug it into the CMA framework.

    The presented solution includes an implementation of a best-fit algorithm.

  2. When requesting memory, devices have to introduce themselves. This way CMA knows who the memory is allocated for. This allows for the system architect to specify which memory regions each device should use.
  3. Memory regions are grouped in various “types”. When device requests a chunk of memory, it can specify what type of memory it needs. If no type is specified, “common” is assumed.

    This makes it possible to configure the system in such a way, that a single device may get memory from different memory regions, depending on the “type” of memory it requested. For example, a video codec driver might want to allocate some shared buffers from the first memory bank and the other from the second to get the highest possible memory throughput.

  4. For greater flexibility and extensibility, the framework allows device drivers to register private regions of reserved memory which then may be used only by them.

    As an effect, if a driver would not use the rest of the CMA interface, it can still use CMA allocators and other mechanisms.

    4a. Early in boot process, device drivers can also request the CMA framework to a reserve a region of memory for them which then will be used as a private region.

    This way, drivers do not need to directly call bootmem, memblock or similar early allocator but merely register an early region and the framework will handle the rest including choosing the right early allocator.

  5. CMA allows a run-time configuration of the memory regions it will use to allocate chunks of memory from. The set of memory regions is given on command line so it can be easily changed without the need for recompiling the kernel.

    Each region has it’s own size, alignment demand, a start address (physical address where it should be placed) and an allocator algorithm assigned to the region.

    This means that there can be different algorithms running at the same time, if different devices on the platform have distinct memory usage characteristics and different algorithm match those the best way.

Use cases

Let’s analyse some imaginary system that uses the CMA to see how the framework can be used and configured.

We have a platform with a hardware video decoder and a camera each needing 20 MiB of memory in the worst case. Our system is written in such a way though that the two devices are never used at the same time and memory for them may be shared. In such a system the following configuration would be used in the platform initialisation code:

static struct cma_region regions[] = { { .name = “region”, .size = 20 << 20 }, { } } static const char map[] __initconst = “video,camera=region”;

cma_set_defaults(regions, map);

The regions array defines a single 20-MiB region named “region”. The map says that drivers named “video” and “camera” are to be granted memory from the previously defined region.

A shorter map can be used as well:

static const char map[] __initconst = “*=region”;

The asterisk (“*”) matches all devices thus all devices will use the region named “region”.

We can see, that because the devices share the same memory region, we save 20 MiB, compared to the situation when each of the devices would reserve 20 MiB of memory for itself.

Now, let’s say that we have also many other smaller devices and we want them to share some smaller pool of memory. For instance 5 MiB. This can be achieved in the following way:

static struct cma_region regions[] = { { .name = “region”, .size = 20 << 20 }, { .name = “common”, .size = 5 << 20 }, { } } static const char map[] __initconst = “video,camera=region;*=common”;

cma_set_defaults(regions, map);

This instructs CMA to reserve two regions and let video and camera use region “region” whereas all other devices should use region “common”.

Later on, after some development of the system, it can now run video decoder and camera at the same time. The 20 MiB region is no longer enough for the two to share. A quick fix can be made to grant each of those devices separate regions:

static struct cma_region regions[] = { { .name = “v”, .size = 20 << 20 }, { .name = “c”, .size = 20 << 20 }, { .name = “common”, .size = 5 << 20 }, { } } static const char map[] __initconst = “video=v;camera=c;*=common”;

cma_set_defaults(regions, map);

This solution also shows how with CMA you can assign private pools of memory to each device if that is required.

Allocation mechanisms can be replaced dynamically in a similar manner as well. Let’s say that during testing, it has been discovered that, for a given shared region of 40 MiB, fragmentation has become a problem. It has been observed that, after some time, it becomes impossible to allocate buffers of the required sizes. So to satisfy our requirements, we would have to reserve a larger shared region beforehand.

But fortunately, you have also managed to develop a new allocation algorithm – Neat Allocation Algorithm or “na” for short – which satisfies the needs for both devices even on a 30 MiB region. The configuration can be then quickly changed to:

static struct cma_region regions[] = { { .name = “region”, .size = 30 << 20, .alloc_name = “na” }, { .name = “common”, .size = 5 << 20 }, { } } static const char map[] __initconst = “video,camera=region;*=common”;

cma_set_defaults(regions, map);

This shows how you can develop your own allocation algorithms if the ones provided with CMA do not suit your needs and easily replace them, without the need to modify CMA core or even recompiling the kernel.

Technical Details

The attributes

As shown above, CMA is configured by a two attributes: list regions and map. The first one specifies regions that are to be reserved for CMA. The second one specifies what regions each device is assigned to.

Regions

Regions is a list of regions terminated by a region with size equal zero. The following fields may be set:

  • size – size of the region (required, must not be zero)
  • alignment – alignment of the region; must be power of two or zero (optional)
  • start – where the region has to start (optional)
  • alloc_name – the name of allocator to use (optional)
  • alloc – allocator to use (optional; and besides alloc_name is probably is what you want)

size, alignment and start is specified in bytes. Size will be aligned up to a PAGE_SIZE. If alignment is less then a PAGE_SIZE it will be set to a PAGE_SIZE. start will be aligned to alignment.

If command line parameter support is enabled, this attribute can also be overriden by a command line “cma” parameter. When given on command line its forrmat is as follows:

regions-attr ::= [ regions [ ‘;’ ] ] regions ::= region [ ‘;’ regions ]

region ::= REG-NAME ‘=’ size [ ‘@’ start ] [ ‘/’ alignment ] [ ‘:’ ALLOC-NAME ]

size ::= MEMSIZE // size of the region start ::= MEMSIZE // desired start address of // the region alignment ::= MEMSIZE // alignment of the start // address of the region

REG-NAME specifies the name of the region. All regions given at via the regions attribute need to have a name. Moreover, all regions need to have a unique name. If two regions have the same name it is unspecified which will be used when requesting to allocate memory from region with given name.

ALLOC-NAME specifies the name of allocator to be used with the region. If no allocator name is provided, the “default” allocator will be used with the region. The “default” allocator is, of course, the first allocator that has been registered. ;)

size, start and alignment are specified in bytes with suffixes that memparse() accept. If start is given, the region will be reserved on given starting address (or at close to it as possible). If alignment is specified, the region will be aligned to given value.

Map

The format of the “map” attribute is as follows:

map-attr ::= [ rules [ ‘;’ ] ] rules ::= rule [ ‘;’ rules ] rule ::= patterns ‘=’ regions

patterns ::= pattern [ ‘,’ patterns ]

regions ::= REG-NAME [ ‘,’ regions ] // list of regions to try to allocate memory // from

pattern ::= dev-pattern [ ‘/’ TYPE-NAME ] | ‘/’ TYPE-NAME // pattern request must match for the rule to // apply; the first rule that matches is // applied; if dev-pattern part is omitted // value identical to the one used in previous // pattern is assumed.

dev-pattern ::= PATTERN // pattern that device name must match for the // rule to apply; may contain question marks // which mach any characters and end with an // asterisk which match the rest of the string // (including nothing).

It is a sequence of rules which specify what regions should given (device, type) pair use. The first rule that matches is applied.

For rule to match, the pattern must match (dev, type) pair. Pattern consist of the part before and after slash. The first part must match device name and the second part must match kind.

If the first part is empty, the device name is assumed to match iff it matched in previous pattern. If the second part is omitted it will mach any type of memory requested by device.

If SysFS support is enabled, this attribute is accessible via SysFS and can be changed at run-time by writing to /sys/kernel/mm/contiguous/map.

If command line parameter support is enabled, this attribute can also be overriden by a command line “cma.map” parameter.

Examples

Some examples (whitespace added for better readability):

cma = r1 = 64M // 64M region @512M // starting at address 512M // (or at least as near as possible) 1M / make sure it’s aligned to 1M :foo(bar); // uses allocator “foo” with “bar” // as parameters for it r2 = 64M // 64M region 1M; / make sure it’s aligned to 1M // uses the first available allocator r3 = 64M // 64M region @512M // starting at address 512M :foo; // uses allocator “foo” with no parameters

cma_map = foo = r1; // device foo with kind==NULL uses region r1

foo/quaz = r2; // OR: quaz = r2; / device foo with kind == “quaz” uses region r2

cma_map = foo/quaz = r1; // device foo with type == “quaz” uses region r1

foo/* = r2; // OR: * = r2; / device foo with any other kind uses region r2

bar = r1,r2; // device bar uses region r1 or r2

baz?/a , baz?/b = r3; // devices named baz? where ? is any character // with type being “a” or “b” use r3

The device and types of memory

The name of the device is taken from the device structure. It is not possible to use CMA if driver does not register a device (actually this can be overcome if a fake device structure is provided with at least the name set).

The type of memory is an optional argument provided by the device whenever it requests memory chunk. In many cases this can be ignored but sometimes it may be required for some devices.

For instance, let’s say that there are two memory banks and for performance reasons a device uses buffers in both of them. Platform defines a memory types “a” and “b” for regions in both banks. The device driver would use those two types then to request memory chunks from different banks. CMA attributes could look as follows:

static struct cma_region regions[] = { { .name = “a”, .size = 32 << 20 }, { .name = “b”, .size = 32 << 20, .start = 512 << 20 }, { } } static const char map[] __initconst = “foo/a=a;foo/b=b;*=a,b”;

And whenever the driver allocated the memory it would specify the kind of memory:

buffer1 = cma_alloc(dev, “a”, 1 << 20, 0); buffer2 = cma_alloc(dev, “b”, 1 << 20, 0);

If it was needed to try to allocate from the other bank as well if the dedicated one is full, the map attributes could be changed to:

static const char map[] __initconst = “foo/a=a,b;foo/b=b,a;*=a,b”;

On the other hand, if the same driver was used on a system with only one bank, the configuration could be changed just to:

static struct cma_region regions[] = { { .name = “r”, .size = 64 << 20 }, { } } static const char map[] __initconst = “*=r”;

without the need to change the driver at all.

Device API

There are three basic calls provided by the CMA framework to devices. To allocate a chunk of memory cma_alloc() function needs to be used:

dma_addr_t cma_alloc(const struct device *dev, const char *type, size_t size, dma_addr_t alignment);

If required, device may specify alignment in bytes that the chunk need to satisfy. It have to be a power of two or zero. The chunks are always aligned at least to a page.

The type specifies the type of memory as described to in the previous subsection. If device driver does not care about memory type it can safely pass NULL as the type which is the same as possing “common”.

The basic usage of the function is just a:

addr = cma_alloc(dev, NULL, size, 0);

The function returns bus address of allocated chunk or a value that evaluates to true if checked with IS_ERR_VALUE(), so the correct way for checking for errors is:

unsigned long addr = cma_alloc(dev, NULL, size, 0); if (IS_ERR_VALUE(addr)) * Error * return (int)addr; * Allocated *

(Make sure to include <linux/err.h> which contains the definition of the IS_ERR_VALUE() macro.)

Allocated chunk is freed via a cma_free() function:

int cma_free(dma_addr_t addr);

It takes bus address of the chunk as an argument frees it.

The last function is the cma_info() which returns information about regions assigned to given (dev, type) pair. Its syntax is:

int cma_info(struct cma_info *info, const struct device *dev, const char *type);

On successful exit it fills the info structure with lower and upper bound of regions, total size and number of regions assigned to given (dev, type) pair.

Dynamic and private regions

In the basic setup, regions are provided and initialised by platform initialisation code (which usually use cma_set_defaults() for that purpose).

It is, however, possible to create and add regions dynamically using cma_region_register() function.

int cma_region_register(struct cma_region *reg);

The region does not have to have name. If it does not, it won’t be accessed via standard mapping (the one provided with map attribute). Such regions are private and to allocate chunk from them, one needs to call:

dma_addr_t cma_alloc_from_region(struct cma_region *reg, size_t size, dma_addr_t alignment);

It is just like cma_alloc() expect one specifies what region to allocate memory from. The region must have been registered.

Allocating from region specified by name

If a driver preferred allocating from a region or list of regions it knows name of it can use a different call simmilar to the previous:

dma_addr_t cma_alloc_from(const char *regions, size_t size, dma_addr_t alignment);

The first argument is a comma-separated list of regions the driver desires CMA to try and allocate from. The list is terminated by a NUL byte or a semicolon.

Similarly, there is a call for requesting information about named regions:

int cma_info_about(struct cma_info *info, const char *regions);

Generally, it should not be needed to use those interfaces but they are provided nevertheless.

Registering early regions

An early region is a region that is managed by CMA early during boot process. It’s platforms responsibility to reserve memory for early regions. Later on, when CMA initialises, early regions with reserved memory are registered as normal regions. Registering an early region may be a way for a device to request a private pool of memory without worrying about actually reserving the memory:

int cma_early_region_register(struct cma_region *reg);

This needs to be done quite early on in boot process, before platform traverses the cma_early_regions list to reserve memory.

When boot process ends, device driver may see whether the region was reserved (by checking reg->reserved flag) and if so, whether it was successfully registered as a normal region (by checking the reg->registered flag). If that is the case, device driver can use normal API calls to use the region.

Allocator operations

Creating an allocator for CMA needs four functions to be implemented.

The first two are used to initialise an allocator for given driver and clean up afterwards:

int cma_foo_init(struct cma_region *reg); void cma_foo_cleanup(struct cma_region *reg);

The first is called when allocator is attached to region. When the function is called, the cma_region structure is fully initialised (ie. starting address and size have correct values). As a meter of fact, allocator should never modify the cma_region structure other then the private_data field which it may use to point to it’s private data.

The second call cleans up and frees all resources the allocator has allocated for the region. The function can assume that all chunks allocated form this region have been freed thus the whole region is free.

The two other calls are used for allocating and freeing chunks. They are:

struct cma_chunk *cma_foo_alloc(struct cma_region *reg, size_t size, dma_addr_t alignment); void cma_foo_free(struct cma_chunk *chunk);

As names imply the first allocates a chunk and the other frees a chunk of memory. It also manages a cma_chunk object representing the chunk in physical memory.

Either of those function can assume that they are the only thread accessing the region. Therefore, allocator does not need to worry about concurrency. Moreover, all arguments are guaranteed to be valid (i.e. page aligned size, a power of two alignment no lower the a page size).

When allocator is ready, all that is left is to register it by calling cma_allocator_register() function:

int cma_allocator_register(struct cma_allocator *alloc);

The argument is an structure with pointers to the above functions and allocator’s name. The whole call may look something like this:

static struct cma_allocator alloc = { .name = “foo”, .init = cma_foo_init, .cleanup = cma_foo_cleanup, .alloc = cma_foo_alloc, .free = cma_foo_free, }; return cma_allocator_register(&alloc);

The name (“foo”) will be used when a this particular allocator is requested as an allocator for given region.

Integration with platform

There is one function that needs to be called form platform initialisation code. That is the cma_early_regions_reserve() function:

void cma_early_regions_reserve(int (*reserve)(struct cma_region *reg));

It traverses list of all of the early regions provided by platform and registered by drivers and reserves memory for them. The only argument is a callback function used to reserve the region. Passing NULL as the argument is the same as passing cma_early_region_reserve() function which uses bootmem and memblock for allocating.

Alternatively, platform code could traverse the cma_early_regions list by itself but this should never be necessary.

Platform has also a way of providing default attributes for CMA, cma_set_defaults() function is used for that purpose:

int cma_set_defaults(struct cma_region *regions, const char *map)

It needs to be called after early params have been parsed but prior to reserving regions. It let one specify the list of regions defined by platform and the map attribute. The map may point to a string in __initdata. See above in this document for example usage of this function.

Future work

In the future, implementation of mechanisms that would allow the free space inside the regions to be used as page cache, filesystem buffers or swap devices is planned. With such mechanisms, the memory would not be wasted when not used.

Because all allocations and freeing of chunks pass the CMA framework it can follow what parts of the reserved memory are freed and what parts are allocated. Tracking the unused memory would let CMA use it for other purposes such as page cache, I/O buffers, swap, etc.