Memory management - partner system algorithm

In general, a high-level operating system must provide basic functions for a process to apply for and release memory of any size at any time, just like malloc function. However, it is not easy to implement malloc function. Because the size of memory applied for by a process is arbitrary, if the operating system does not implement malloc function in the right way, it will directly lead to an impossibility The problem to avoid is memory fragmentation.

Memory fragmentation is that memory is divided into small and small blocks. Although these blocks are idle, they are too small to be used. As the number of requests and releases increases, memory becomes more and more discontinuous. Finally, there will be only fragments left in the whole memory. Even if there are enough free page frames to satisfy the request, it may not be satisfied to allocate a large continuous page frame. Therefore, the core of reducing memory waste is to avoid memory fragments as much as possible.

To solve this problem, there are many effective solutions, among which partner algorithm is proved to be a very effective memory management method, so it is also adopted by quite a number of operating systems.

Principle of partner algorithm

Linux uses this famous partner system algorithm to solve the problem of external fragmentation. All the free page frames are divided into 11 linked lists, each containing 1, 2, 4, 8, 16, 32, 64128256512 and 1024 consecutive page frames. The maximum request for 1024 page frames corresponds to a 4MB continuous RAM block. The physical address of the first page box of each block is an integer multiple of the block size. For example, a block of 16 page boxes has a starting address that is a multiple of 16 * 2 ^ 12 (2 ^ 12 = 4096, which is the size of a regular page).

Here is a simple example to illustrate the working principle of the algorithm:

Suppose you want to request a block of 256 (129-256) page boxes. The algorithm first checks whether there is a free block in the list of 256 page frames. If there is no such block, the algorithm will look for the next larger page block, that is, a free block in the 512 page box linked list. If there is such a block, the kernel divides 512 page frames into two parts, which are generally used to meet the needs, and the other half is inserted into the linked list of 256 page frames. If no free block is found in the block list of 512 page frames, continue to find a larger block - 1024 page frames. If such a block exists, the kernel uses 256 page frames of 1024 page frame blocks as requests, and then inserts 512 of the remaining 768 page frames into the 512 page frame linked list, and then inserts the last 256 into the 256 page frame linked list. If the list of 1024 page boxes is still empty, the algorithm will give up and send an error signal.

Relevant data structure

#define MAX_ORDER 11
struct zone {
	struct free_area	free_area[MAX_ORDER];
struct free_area {
	struct list_head	free_list;
	unsigned long		nr_free;//The number of free category blocks in this group

The k-th element of the free ﹣ area array in the Zone structure holds all free blocks with a continuous size of 2^k, which is realized by inserting the first page of the continuous page into the free ﹣ list. The private field of the page descriptor of the first page of the continuous page indicates which order linked list the changed part of the continuous page belongs to.

Partner algorithm system initialization

When the Linux kernel starts, the partner algorithm is not available. Linux uses bootmem to manage memory. In MEM init
The free memory block in the bootmem bitmap is inserted into the free list of the partner algorithm system.
The calling process is as follows

//Using free page to distribute pages to Partner Manager
    return(free_all_bootmem_core(NODE_DATA(0)));  //#define NODE_DATA(nid)		(&contig_page_data)
        bootmem_data_t *bdata = pgdat->bdata;
        page = virt_to_page(phys_to_virt(bdata->node_boot_start));
		idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
		map = bdata->node_bootmem_map;
		for (i = 0; i < idx; ) 
			unsigned long v = ~map[i / BITS_PER_LONG];
			//If 32 pages are free
			if (gofast && v == ~0UL)
				count += BITS_PER_LONG;
				order = ffs(BITS_PER_LONG) - 1;
				//Set the reference count of 32 pages to 1
				set_page_refs(page, order)
				//Release 32 pages to free list at one time
				__free_pages(page, order);
				i += BITS_PER_LONG;
				page += BITS_PER_LONG;
			//Of the 32 pages, only some are free	
			else if (v)
				for (m = 1; m && i < idx; m<<=1, page++, i++)
					if (v & m)
						set_page_refs(page, 0);
						//Release a single page
				page += BITS_PER_LONG;
		//Free memory allocation bitmap itself		
		page = virt_to_page(bdata->node_bootmem_map);
		for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++)
			set_page_count(page, 1);

Partner algorithm system allocation space

page = __rmqueue(zone, order);
	//Starting from the requested order, scan each available block list for a circular search.
    for (current_order = order; current_order < MAX_ORDER; ++current_order)
        area = zone->free_area + current_order;
        if (list_empty(&area->free_list))
        page = list_entry(area->, struct page, lru);  
		//First, delete the first page box descriptor in the free block list.
		//Be clear about the private field of the first page box descriptor, which indicates the chain list of which size the continuous page box belongs to
        zone->free_pages -= 1UL << order;
		//If you apply from a larger order list, the rest will be reinserted into the list
        return expand(zone, page, order, current_order, area);
            unsigned long size = 1 << high;
            while (high > low)
                size >>= 1; 
				//This part of continuous page is inserted into the corresponding free list
                list_add(&page[size].lru, &area->free_list); 
				//Set the order of the continuous page of this part
                set_page_order(&page[size], high);
                    page->private = order;
                         __set_bit(PG_private, &(page)->flags)
            return page;

Partner algorithm system reclaims space

	//The linux kernel divides the space into three areas, namely, zone? DMA, zone? Normal, and zone? High. The zone? MEM? Map field is the first page descriptor pointing to the area
    struct page *base = zone->zone_mem_map;
    while (!list_empty(list) && count--)  
        page = list_entry(list->prev, struct page, lru);
            int order_size = 1 << order;
			//Subscript of the first page of the space
            page_idx = page - base; 
            zone->free_pages += order_size;
			//Loop up to 10 - order times. Each time a block is merged with its partner.
            while (order < MAX_ORDER-1)
				//Find a partner. If page_idx=128, order=4, then buddy_idx=144
                buddy_idx = (page_idx ^ (1 << order)); 
                buddy = base + buddy_idx;
                 * Determine whether the partner block is the first page of the free page box with the size of order.
                 * First, the first page of the partner must be free (_count == -1)
                 * At the same time, it must belong to dynamic memory (PG_reserved is cleared to 0,PG_reserved to 1 means it is reserved for the kernel or not used)
                 * Finally, its private field must be order
                if (!page_is_buddy(buddy, order))
                area = zone->free_area + order;
				//Reduction of free pages in the original area
                    page->private = 0;
                page_idx &= buddy_idx;

			 * Partner cannot be merged with current block.
			 * Insert the block into the appropriate linked list and update the private field of the first page box with a block size order.
            coalesced = base + page_idx;
            set_page_order(coalesced, order);
            list_add(&coalesced->lru, &zone->free_area[order].free_list);
Published 56 original articles, won praise 8, and visited 130000+
Private letter follow

Tags: Linux REST

Posted on Wed, 05 Feb 2020 01:40:42 -0800 by achilles