What is linux slab

Анатомия распределителя памяти slab в Linux

Эта статья описывает идеи, лежащие в основе механизма slab allocator (распределитель slab), и исследует его интерфейсы и приемы использования. Статья сфокусирована на описании механизмов, предоставляемых ядром Linux для управления памятью и, в частности, на механизмах, предоставляемых slab allocation.

Re: Анатомия распределителя памяти slab в Linux

надо понимать так, что вместо выгнанного анестезиолога-кардиолога в кернел-хакеры приняли паталогоанатома ?

Re: Анатомия распределителя памяти slab в Linux

А чем эта статья лучше соответствующего раздела у Р. Лава?

Re: Анатомия распределителя памяти slab в Linux

Так вроде щас же продвигается SLUB allocator? или он ниче принципиально не отличается?

Re: Анатомия распределителя памяти slab в Linux

Только у меня одного SLUB?

Re: Анатомия распределителя памяти slab в Linux

А не баян ли статья по ссылке?

Re: Анатомия распределителя памяти slab в Linux

> А не баян ли статья по ссылке?

а ты сходи. Статья скучновата.

Re: Анатомия распределителя памяти slab в Linux

Re: Анатомия распределителя памяти slab в Linux

слаб аллокатор у линукса . слаб

Re: Анатомия распределителя памяти slab в Linux

Тлять, вот загадка — какие чудаки в IBM это переводят?

Статья в общем правильная, нужная.

Но тля, читать невозможнонах.

Re: Анатомия распределителя памяти slab в Linux

в Linux есть три аллокатора: SLAB (стандартный), SLOB (вроде когда памяти мало, типа мобильника), SLUB (опционально в 2.6.22+, на смену SLAB).

Re: Анатомия распределителя памяти slab в Linux

> слаб аллокатор у линукса . слаб

Че, аллокатор не встает на доступную память?

Re: Анатомия распределителя памяти slab в Linux

не будет лишним сказать, что в FreeBSD так же используется slab like allocator (начальная поддержка в 5-CURRENT, 2002 г)

Re: Анатомия распределителя памяти slab в Linux

Пришел поручик и все опошлил 🙁

Re: Анатомия распределителя памяти slab в Linux

Re: Анатомия распределителя памяти slab в Linux

Нет, не только у тебя 🙂 Я тоже ради интереса выбрал.

Re: Анатомия распределителя памяти slab в Linux

>Нет, не только у тебя 🙂 Я тоже ради интереса выбрал.

ну и как? разница есть? и если есть, то в какую сторону?

Re: Анатомия распределителя памяти slab в Linux

По ощущениям — не заметил ничего.

Re: Анатомия распределителя памяти slab в Linux

Перевод МОЩЩ ! Дошел до фразы «обращение к деконструктору», дальше читать не стал, осознав, что термин «деструктор» переводчику явно не знаком.

Re: Анатомия распределителя памяти slab в Linux

>Перевод МОЩЩ ! Дошел до фразы «обращение к деконструктору», дальше читать не стал, осознав, что термин «деструктор» переводчику явно не знаком.

Пейсателю оригинальной статьи надо оторвать яйца, ибо термин «destructor» ему тоже явно не знаком, и он везде использует связку «constructor/deconstructor». Переводчик же на это повелся, и как следствие, так же останется без яиц.

Re: Анатомия распределителя памяти slab в Linux

> Пейсателю оригинальной статьи надо оторвать яйца, ибо термин «destructor» ему тоже явно не знаком

Отрывать яйца за неиспользование кривой терминологии приплюснутых сектантов? Суровы вы батенька.

Re: Анатомия распределителя памяти slab в Linux

>> Пейсателю оригинальной статьи надо оторвать яйца, ибо термин «destructor» ему тоже явно не знаком

>Отрывать яйца за неиспользование кривой терминологии приплюснутых сектантов? Суровы вы батенька.

Ммм, эта терминология давно уже перестала принадлежать приплюснутым секантам.

Re: Анатомия распределителя памяти slab в Linux

Приплюс-плюснутые как раз назвали бы конструктор фабрикой мьютексов

Re: Анатомия распределителя памяти slab в Linux

>По ощущениям — не заметил ничего.

а по измерениям? или не мерял ничего?

Re: Анатомия распределителя памяти slab в Linux

Ничего не мерял — некогда, честно говоря, искать методику измерения.

Источник

Slob, Slab VS Slub

Overview

First, «slab» has become a generic name referring to a memory allocation strategy employing an object cache, enabling efficient allocation and deallocation of kernel objects. It was first documented by Sun engineer Jeff Bonwick and implemented in the Solaris 2.4 kernel.1

Linux currently offers three choices for its «slab» allocator :

Slab is the original, based on Bonwick’s seminal paper and available since Linux kernel version 2.2. It is a faithful implementation of Bonwick’s proposal, augmented by the multiprocessor changes described in Bonwick’s follow-up paper2.

Slub is the next-generation replacement memory allocator, which has been the default in the Linux kernel since 2.6.23. It continues to employ the basic «slab» model, but fixes several deficiencies in Slab’s design, particularly around systems with large numbers of processors. Slub is simpler than Slab.

SLOB (Simple List Of Blocks) is a memory allocator optimized for embedded systems with very little memory—on the order of megabytes. It applies a very simple first-fit algorithm on a list of blocks, not unlike the old K&R-style heap allocator. In eliminating nearly all of the overhad from the memory allocator, SLOB is a good fit for systems under extreme memory constraints, but it offers none of the benefits described in 1 and can suffer from pathological fragmentation.

slub allocator

Linux’s physical memory management uses the buddy system (buddy system) in units of pages, but in many cases, the kernel only needs a small object space, and these small spaces are variable and unpredictable for different objects. Yes, so a management mechanism similar to user space heap memory (malloc/free) is needed. However, the kernel’s management of objects has certain particularities. Some objects are accessed very frequently and need to use a buffer mechanism; the organization of objects needs to consider the impact of hardware cache; needs to consider the impact of multiprocessor and NUMA architecture. In the early 1990s, in the Solaris 2.4 operating system, a buffer allocation and management method called «slab» (originally a large piece of concrete) was adopted, which met the special needs of the kernel to a considerable extent.

For many years, SLAB has become the mainstream algorithm for Linux kernel object buffer management, and no one is even willing to modify it for a long time, because it is really very complicated, and in most cases, its work is done quite well. However, with the wide application of large-scale multi-processor systems and NUMA systems, SLAB allocators have gradually exposed their own serious shortcomings:

1). Cache queue management is complex;

2). High management data storage overhead;

3). Complex support for NUMA;

4). Difficulty in debugging and tuning;

5). Abandon the slab coloring mechanism with less obvious effect;

In response to these SLAB deficiencies, kernel developer Christoph Lameter introduced a new solution in Linux kernel 2.6.22: SLUB allocator. The SLUB allocator is characterized by simplifying the design concept while retaining the basic idea of ​​the SLAB allocator: each buffer is composed of multiple small slabs, and each slab contains a fixed number of objects. SLUB allocator simplifies kmem_cache, slab and other related management data structures, abandons many queue concepts in SLAB allocator, and optimizes for multi-processor and NUMA systems, thereby improving performance and scalability and reducing memory waste . In order to ensure that other modules of the kernel can be seamlessly migrated to the SLUB allocator, SLUB also retains all the interface API functions of the original SLAB allocator.

(Note: The source code analysis of this article is based on linux-4.1.x)

The overall data structure relationship is shown in the following figure:

1 SLUBInitialization of the allocator

SLUB initialization has two important tasks: first, create kmem_cache for struct kmem_cache and struct kmem_cache_node; second, create kmem_cache for regular kmalloc.

1.1 Apply for kmem_cacheKmem_cache

The first work involves a «chicken or egg» problem, because creating kmem_cache needs to apply from the kmem_cache buffer, and at this time, the kmem_cache buffer has not been created. The kernel’s solution is to first use two static variables boot_kmem_cache and boot_kmem_cache_node to save the struct kmem_cach and struct kmem_cache_node buffer management data, and use the two static variables as the basis to apply for a slub buffer with the size of the struct kmem_cache and struct kmem_cache_node objects, and then Apply for two kmem_caches from these buffers, and copy the contents of boot_kmem_cache and boot_kmem_cache_node to the newly applied object, thus completing the bootstrap (self-guided) of the struct kmem_cache and struct kmem_cache_node management structures.

1.2 Create kmallocRegular cache

In principle, the system will apply for a cache for each memory block of the power of 2 size, but if the memory block is too small, a lot of fragmentation will be wasted, so the system also creates a cache for 96B and 192B. So a size_index array is used to help determine which cache is used for memory blocks smaller than 192B

2 Cache creation and destruction

2.1 Cache creation

The cache is created through the interface kmem_cache_create. Before creating a new cache, try to find a cache that can be merged. The merge conditions include the judgment of the object size and cache attributes. If it can be merged, it will directly return to the existing kmem_cache and create a kobj link to point to The same node.

Creating a new cache is mainly to apply for and initialize the space temporarily used by the management structure. These management structures include kmem_cache, kmem_cache_nodes, kmem_cache_cpu. At the same time, create a kobject node in sysfs. Finally, kmem_cache is added to the global cahce linked list slab_caches.

2.2 Cache destruction

The destruction process is much simpler than the creation process. The main work is to release all pages in the partial queue, release kmem_cache_cpu, release kmem_cache_node of each node, and finally release kmem_cache itself.

3 Application object

The object is the memory unit that can be allocated in the SLUB allocator. Compared with the SLAB, the organization of the SLUB object is very simple and the application process is more efficient. SLUB does not have any management area structure to manage objects, but embeds the association between objects in the memory of the object itself, because the applicant does not care about the contents of the memory before the object is allocated. Moreover, the association between each SLUB is also processed using the structure of the page itself.

Each CPU has a slab as a local cache. As long as the node where the slab is located matches the node requested by the applicant, and there are free objects in the slab, the free objects are taken out directly from cpu_slab, otherwise the slow path is entered.

The offset offset of each object memory stores the next free object. The offset is usually 0, which means that the first word of the object memory is reused to save the pointer of the next free object. When the condition (flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) Or when there is an object constructor, offset is not 0, and the structure of each object is as shown in the figure below.

The freelist of cpu_slab holds the address of the current first free object.

If there are no free objects in the local CPU cache, apply for a new slab; if there are free objects but the memory node does not match, deactive the current cpu_slab and apply for a new slab.

deactivate_slab mainly performs two steps:

The first step is to release all the freelist of cpu_slab back to page->freelist;

The second part is to perform different operations according to the state of the page (slab). If the slab has some free objects, move the page to the partial queue of kmem_cache_node; if the slab is all free, directly release the slab; if the slab is all occupied , And the CONFIG_SLUB_DEBUG compilation option is turned on, then the page is moved to the full queue.

The status of the page is also changed from frozen to unfrozen. (Frozen stands for slab in cpu_slub, unfroze stands for partial queue or full queue).

There are two situations for applying for a new slab. If the partial queue of cpu_slab is not empty, the next page in the queue is taken out as the new cpu_slab, and at the same time, whether the memory node matches is checked again, and if it does not match, it will be processed in a loop.

If the partial queue of cpu_slab is empty, check whether the partial queue of this node is empty. If it is not empty, then take out the page; if it is empty, look at the partial queues of other nodes within a certain distance. If it is still empty, you need to Create a new slab.

Creating a new slab is actually applying for a memory page corresponding to the order, which is used to put a sufficient number of objects. It is worth noting that the order and the number of objects are determined, the two influence each other. The order and the number of objects are stored in the kmem_cache member kmem_cache_order_objects at the same time, the lower 16 bits are used to store the number of objects, and the higher bits store the order. The relationship between order and the number of objects is very simple: ((PAGE_SIZE

Let’s focus on the function calculate_order

4 Release object

It can also be seen from the above application process that the released object has several places:

1) CPU local cache slab, which is cpu_slab;

2) Put it back into the page (that is, slab) where the object is located; in addition, deal with the slab where it is located:

2.1) If the slab is completely empty after putting it back, the slab will be destroyed directly;

2.2) If the slab is full before putting it back, it is judged whether the slab has been frozen; if it is frozen, no other work is needed; if it is not frozen, it will be frozen and put into the partial queue of cpu_slab; if the cpu_slab partial queue If there are too many, all slabs in the queue will be unfrozen into the partial queue of their respective node at one time.

It is worth noting that the function of the cpu partial queue is an option and depends on the kernel option CONFIG_SLUB_CPU_PARTIAL. If it is not enabled, the cpu partial queue is not used, and the partial queue of each node is used directly.

Analysis of Linux slab allocator

M. Jones, published September 20, 2010

Dynamic memory management

The goal of memory management is to provide a way to realize memory sharing among users for various purposes. The memory management method should implement the following two functions:

• Minimize the time required to manage memory
• Maximize available memory for general applications (minimize management overhead)

Memory management is actually a zero-sum game about trade-offs. You can develop an algorithm that uses a small amount of memory for management, but it takes more time to manage the available memory. It is also possible to develop an algorithm to efficiently manage memory, but with more memory. Ultimately, the needs of a particular application will prompt the choice of this trade-off.

Each memory manager uses a heap-based allocation strategy. In this method, large blocks of memory (calledheap) Is used to provide memory for user-defined purposes. When users need a piece of memory, they request to allocate a certain size of memory to themselves. The heap manager looks at the available memory (using a specific algorithm) and returns a block of memory. Some algorithms used in the search process arefirst-fit(The first memory block that satisfies the request searched in the heap) andbest-fit(Use the most suitable memory block in the heap that satisfies the request). When the user finishes using the memory, the memory is returned to the heap.

The fundamental problem with this heap-based allocation strategy isFragmentation. When memory blocks are allocated, they will be returned at different times in different orders. This will leave some holes in the heap, and it will take some time to effectively manage free memory. This algorithm usually has a higher memory efficiency (allocation of required memory), but it takes more time to manage the heap.

Another method is calledbuddy memory allocation, Is a faster memory allocation technology, it divides the memory into power-of-two partitions, and uses the best-fit method to allocate memory requests. When the user releases the memory, it will check the buddy block to see if its adjacent memory block has also been released. If so, the memory blocks will be merged to minimize memory fragmentation. This algorithm is more time efficient, but due to the best-fit method, it will waste memory.

This article will focus on the memory management of the Linux kernel, especiallyslab distributionThe mechanism provided.

slab cache

The basis of the slab allocator used by Linux is an algorithm first introduced by Jeff Bonwick for the SunOS operating system. Jeff’s allocator revolves around object caching. In the kernel, a large amount of memory is allocated for a limited set of objects (such as file descriptors and other common structures). Jeff found that the time required to initialize ordinary objects in the kernel exceeds the time required to allocate and release them. So his conclusion is that the memory should not be released back to a global memory pool, but the memory should be kept in a state initialized for a specific purpose. For example, if the memory is allocated to a mutex, then the mutex initialization function only needs to be executed once when the mutex is first allocated memory ( mutex_init ) OK. Subsequent memory allocation does not need to execute this initialization function, because it is already in the required state since the last release and destructor call.

The Linux slab allocator uses this and other ideas to build a memory allocator that is efficient in space and time.

Figure 1 shows the high-level organizational structure of the slab structure. At the top is cache_chain , This is a slab cached link list. This is very useful for the best-fit algorithm, which can be used to find the cache that best fits the required allocation size (traversing the list). cache_chain Each element of is one kmem_cache The reference to the structure (called acache). It defines a pool of objects of a given size to be managed.

Figure 1. The main structure of the slab distributor

Each cache contains oneslabsList, this is a contiguous memory block (usually pages). There are 3 types of slabs:

slabs_full

Fully allocated slab

slabs_partial

Partially allocated slab

slabs_empty

Empty slab, or no objects are allocated

Note slabs_empty Slab in the list isRecycling (reaping)The main candidates. It is through this process that the memory used by the slab is returned to the operating system for other users to use.

Each slab in the slab list is a contiguous memory block (one or more contiguous pages), which are divided into objects. These objects are the basic elements for allocation and release from a specific cache. Note that slab is the smallest allocation unit for the operation of the slab allocator, so if the slab needs to be expanded, this is the minimum expanded value. Generally speaking, each slab is assigned to multiple objects.

Since objects are allocated and released from slabs, a single slab can be moved between slab lists. For example, when all objects in a slab are used up, slabs_partial Move to the list slabs_full List. When a slab is completely allocated and objects are released, slabs_full Move to the list slabs_partial List. When all objects are released, start from slabs_partial List moved to slabs_empty List.

The motivation behind slab

Compared with the traditional memory management mode, the slab cache allocator provides many advantages. First, the kernel usually relies on the allocation of small objects, which will be allocated countless times during the system life cycle. The slab cache allocator provides this function by caching objects of similar size, thereby avoiding common fragmentation problems. The slab allocator also supports the initialization of common objects, thus avoiding repeated initialization of an object for the same purpose. Finally, the slab allocator can also support hardware cache alignment and coloring, which allows objects in different caches to occupy the same cache line, thereby improving cache utilization and obtaining better performance.

API function

Now let’s look at the application programming interface (API) that can create a new slab cache, add memory to the cache, destroy the cache, and the functions in the slab that allocate and release objects.

The first step is to create a slab cache structure, you can create it statically as:

Then other slab cache functions will use the reference to create, delete, and allocate. kmem_cache The structure contains the data of each central processing unit (CPU), a set of adjustable parameters (accessible through the proc file system), statistical information, and elements necessary for managing the slab cache.

kmem_cache_create

Kernel function kmem_cache_create Used to create a new cache. This is usually performed when the kernel is initialized, or when the kernel module is first loaded. The prototype is defined as follows:

name The parameter defines the cache name, and the proc file system (in /proc/slabinfo) uses it to identify the cache. To size The parameter specifies the size of the object created for this cache, align The parameters define the necessary alignment of each object. To flags The parameter specifies the options that are enabled for caching. These signs are shown in Table 1.

Table 1. Some options of kmem_cache_create (specified in the flags parameter)

Options	Description
SLAB_RED_ZONE	Insert flags at the head and tail of the object to support checking for buffer overflow.
SLAB_POISON	Use a known pattern to fill the slab, allowing monitoring of objects in the cache (objects are owned by objects, but can be modified externally).
SLAB_HWCACHE_ALIGN	The specified cache object must be aligned with the hardware cache line.

ctor with dtor The parameter defines an optional object constructor and destructor. The constructor and destructor are callback functions provided by the user. When a new object is allocated from the cache, it can be initialized through the constructor.

After creating the cache, kmem_cache_create The function will return a reference to it. Note that this function does not allocate any memory to the cache. Conversely, when trying to allocate an object from the cache (which is initially empty),refillThe operation allocates memory to it. When all objects are used, you can also add memory to the cache through the same operation.

kmem_cache_destroy

Kernel function kmem_cache_destroy Used to destroy the cache. This call is executed by the kernel module when it is unloaded. When calling this function, the cache must be empty.

kmem_cache_alloc

To allocate an object from a named cache, you can use kmem_cache_alloc Function. The caller provides the cache from which the object is allocated and a set of flags:

void kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags );

This function returns an object from the cache. Note that if the cache is currently empty, then this function will be called cache_alloc_refill Add memory to the cache. To kmem_cache_alloc The flags option and kmalloc The flags options are the same. Table 2 gives a partial list of flag options.

Table 2. Flag options of kmem_cache_alloc and kmalloc kernel functions

Sign	Description
GFP_USER	Allocate memory for the user (this call may sleep).
GFP_KERNEL	Allocate memory from kernel RAM (this call may sleep).
GFP_ATOMIC	Make the call force non-sleep (very useful for interrupt handlers).
GFP_HIGHUSER	Allocate memory from high-end memory.

kmem_cache_zalloc

Kernel function kmem_cache_zalloc versus kmem_cache_alloc Similar, except that it executes on the object memset Operation, used to clean up the object before returning it to the caller.

kmem_cache_free

To release an object back to slab, you can use kmem_cache_free . The caller provides the cache reference and the object to be released.

void kmem_cache_free( struct kmem_cache *cachep, void *objp );

kmalloc and kfree

The most commonly used memory management function in the kernel is kmalloc with kfree Function. The prototypes of these two functions are as follows:

void *kmalloc( size_t size, int flags );

void kfree( const void *objp );

Pay attention to kmalloc In, the only two parameters are the size of the object to be allocated and a set of flags (seeTable 2Part of the list in ). But kmalloc with kfree A slab cache similar to the previously defined function is used. kmalloc Instead of naming a certain slab cache from which to allocate objects, it loops through the available caches to find a cache that can meet the size limit. After finding it, (use __kmem_cache_alloc ) Assign an object. need to use kfree Release the object, the cache from which the object is allocated can be called virt_to_cache OK. This function will return a cache reference, and then __cache_free Use this reference to release the object in the call.

Other functions

The slab cache API also provides some other very useful functions. kmem_cache_size The function returns the size of the objects managed by this cache. You can also call kmem_cache_name To retrieve the name of a given cache (defined when the cache is created). The cache can be shrunk by releasing idle slabs. This can be done by calling kmem_cache_shrink Realize. Note that this operation (called recycling) is performed automatically by the kernel periodically (through kswapd ）。

unsigned int kmem_cache_size( struct kmem_cache *cachep );

const char *kmem_cache_name( struct kmem_cache *cachep );

int kmem_cache_shrink( struct kmem_cache *cachep );

Example usage of slab cache

The following code snippet shows the process of creating a new slab cache, allocating and releasing objects from the cache, and then destroying the cache. First, you must define a kmem_cache The object, and then initialize it (see Listing 1). This particular cache contains 32-byte objects and is hardware cache aligned (by the flag parameter SLAB_HWCACHE_ALIGN Definition).

Источник