Slab allocation

This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( ) Reason: Unnecessary general remarks; No meaningful article structure; Clear definition is missing. The English article can be used for the repair.

The slab allocator is a method for managing memory, which use many operating systems and applications. The algorithm is aimed that, in the frequently occurring smaller reservation memory areas of the memory is known as efficiently as possible, ie with little wastage utilized.

Note: Some details of the present technical description of the slab allocators are based on the implementation in the Linux kernel 2.6.10 - rc2. This may differ from other systems and may be not technically up to date

• 3.1 Tasks
• 3.2 Structure
• 3.3 Example: information about the caches
• 3.4 fragmentation 3.4.1 Internal fragmentation
• 3.4.2 External fragmentation

• 5.1 Structure
• 5.2 The administration of free objects

History

The slab allocator was developed in 1994 by Jeff Bonwick for SunOS 5.4. Since he has his approach publicly documented, it has been adopted by many other operating systems (eg Linux) and applications (eg, Perl). In 2001, Bonwick released a significantly improved version that was well documented publicly.

1999 held the slab allocator entry into the Linux kernel. The current implementation already contains some elements from Bonwicks 2001's version, but this is not yet fully implemented.

Idea

The goal of memory management it should be possible to efficiently use the available memory and to enable a quick release and reservation of the required objects. Here also the problem of fragmentation is not negligible: it should occur during operation as little small, unused memory regions between the used. (For IA -32: 4096 bytes ) For technical reasons, the memory is organized in very large memory pages, but this is not particularly efficient for dynamically allocated memory.

Properties of nuclear objects

Most objects that uses an operating system that are relatively small and have a limited life, are thus returned to the system after a short time. Also multiple objects of the same type are often required.

Private caches

Bonwick distances itself in its elaboration of the idea of private caches, so cache that manages each process or each kernel module in the operating system itself. Although a process itself has the best overview of the own storage needs, but he has almost no overview of the storage situation in the system as a whole and not on the needs of other processes.

Clients & Central Allocator

Bonwick divided memory management therefore in two parts. The Central allocator provides functions to manage the memory. It ensures the most efficient use. This contrasts with the clients. They describe only the objects you need and do not need to worry about the details.

Structure of the Central allocators

The following structure is proposed by Bonwick:

• Objects of the same type are to Slabs (English: Tile, tile ) summarized.
• These slabs are arranged at a cache, that it further objects of the same type can be kept in stock.
• This caching reduces costly recourse to the overlying buddy memory management, which provides only whole memory pages.
• The memory pages required for slabs and caches must be fetched from the buddy system.

In other words, the slab allocator divides the memory provided by the buddy system to continue. The Central Allocator provides interfaces (APIs), through which clients can request memory.

Caches

Tasks

The caches have three tasks:

• Make supplies of frequently used objects ready initialized available.
• They are general stocks of objects of certain sizes are available ( often needed for fewer objects or individual storage areas ), under Linux up bytes.
• They should take advantage of the hardware cache (TLB, L1 cache) as well as possible.

Construction

Each cache is (under Linux type: kmem_cache_s ) by a data structure represents. This includes three doubly linked lists ( within the subtree list of type kmem_list3 ) under which the slabs are strung. A list of the slabs, which are filled only with unused objects ( "all free "), a wholly with the objects in use ( "all used" ), and the third list contains Slabs with used and not currently used objects ( " mixed free / used ").

Furthermore, there are (since the 2001 version of it Bonwicks elaboration) a buffer ( array_cache type ) for each processor in the system, which remembers the last shared objects. These objects are also first awarded again, as the probability is very high, they can still be found in one of the processor caches so thus better utilized.

For example, information about the caches

The example of this concept is evident. There are Linux run-time information to the slab allocator in the file / proc / slabinfo. The following sample output is greatly reduced.

Meaning of the columns:

• Name: name of the cache
• : Number of objects currently in use
• : The number of objects
• : size of an object (in bytes)
• : Number of objects per slab
• : number of pages per slab
• : Number of objects created at once or be released ( the performance and release of a slab )

The first part of the table shows the already mentioned caches for certain objects, the second part of the caches in general sizes, depending. , In a variant for DMA -capable memory and for non- DMA -capable memory

Fragmentation

Fragmentation can be divided into two types divide: Internal and external fragmentation.

Internal fragmentation

Internal fragmentation Bonwick defined as " by buffers wasted space", ie the space that is wasted per slab. Unused gaps caused by:

The blend at the end is smaller than the Slabgröße, it can thus be influenced by the size of the slab, the greater the slab, the more objects it contains and the smaller of the blend. Furthermore, this blend for the so-called Colouring used, which is discussed further below.

External fragmentation

External fragmentation Bonwick defined as "unused buffers in the free list", ie unused objects in the slab. As can be seen already in the table above, external fragmentation exists in this method. However, it is relatively low.

The fact that equal objects have similar lifetimes, caused a few partially used slabs. Most slabs are either completely or not at all busy. The exception to this are the caches in certain sizes, but these are not used as frequently.

Furthermore, the memory is not divided, as do other methods (for example, the buddy method ). Because the more the objects in a slab, the higher the external fragmentation, since the probability to get a completely empty slab decreases.

Colouring

Colouring the attempt to make better use of by different orientation of the same objects in different slabs, the CPU cache.

For this, the waste is taken at the end of the slab and pasted parts of it before the first object in the slab. Thus, the objects are " offset " in comparison to another slab. Can be reduced by skillfully aligning to multiple of the cache line size by a mutual displacement of the objects from the cache as well as the addresses in the TLB.

Sequence of a memory request

From the previous results in the typical sequence of a memory request:

The negative effect on the cache and thus the performance increases from point to point.

Slabs

Construction

A slab consists of

The administration of free objects

The administration of the free objects runs in the Linux kernel on a list of integers. It contains just as many numbers as slab objects. Each number field only has meaning if the corresponding object is not used, and then the index of the next free object. By the information on the first object in the free head of the slab can therefore be quickly determined and returned to the next.