{"id":455,"date":"2020-08-18T19:23:47","date_gmt":"2020-08-18T20:23:47","guid":{"rendered":"http:\/\/www.linux-tutorial.info\/?page_id=77"},"modified":"2020-08-22T19:26:17","modified_gmt":"2020-08-22T20:26:17","slug":"this-is-the-page-title-toplevel-288","status":"publish","type":"page","link":"http:\/\/www.linux-tutorial.info\/?page_id=455","title":{"rendered":"Page Allocation and Deallocation"},"content":{"rendered":"\n<title>Page Allocation and Deallocation<\/title>\nThere are many demands on the physical pages in the system.\nFor example, when an image is loaded into memory the operating system\nneeds to allocate pages.\nThese will be freed when the image has finished executing and is\nunloaded.\nAnother use for physical pages is to hold kernel specific data structures\nsuch as the page tables themselves.\nThe mechanisms and data structures used for page allocation and\ndeallocation are perhaps the most critical in maintaining the efficiency\nof the virtual memory subsystem.\n<p>\nAll of the physical pages in the system are described by the\n<tt>mem_map<\/tt> data structure which is a list of <tt>mem_map_t**<\/tt>\nstructures which is initialized at boot time.\nEach <tt>mem_map_t<\/tt> describes a single physical page in the system.\nImportant fields (so far as memory management is concerned) are:\n<dl compact>\n<p>\n\t<dt><b>count<\/b><\/dt><dd> This is a count of the number of users of this page.\n\tThe count is greater than one when the page is shared between many\n\tprocesses,\n\t<dt><b>age<\/b><\/dt><dd> This field describes the age of the page and is used\n\tto decide if the page is a good candidate for discarding or\n\tswapping,\n\t<dt><b>map_nr<\/b><\/dt><dd> This is the physical page frame number that this <tt>mem_map_t<\/tt> describes.\n<\/dl>\n<p>\nThe <tt>free_area<\/tt> vector is used by the page allocation code\nto find and free pages.\nThe whole buffer management scheme is supported by this mechanism and, as\nfar as the code is concerned, the size of the page and physical paging\nmechanisms used by the processor are irrelevant.\n<p>\nEach element of <tt>free_area<\/tt> contains information about blocks of\npages.  The first element in the array describes single pages, the next blocks of 2 pages, the next\nblocks of 4 pages and so on upwards in powers of two.\nThe <tt>list<\/tt> element is used as a queue head and has pointers to the\n<tt>page<\/tt> data structures in the <tt>mem_map<\/tt> array.   Free blocks of pages are queued here.\n<tt>map<\/tt> is a pointer to a bitmap which keeps track of allocated groups of\npages of this size.\nBit N of the bitmap is set if the Nth block of pages is free.\n<p>\nThe figure below, shows the <tt>free_area<\/tt> structure.\nElement 0 has one free page (page frame number 0) and element 2 has 2 free blocks of 4 pages, the\nfirst starting at page frame number 4 and the second at page frame number 56.\n<p>\n<h3>Page Allocation<\/h3>\n<p>\nLinux uses the Buddy algorithm\n<a href=\"#tthFtNtAAC\" name=tthFrefAAC><sup>2<\/sup><\/a>\nto effectively allocate and deallocate blocks of pages.\nThe page allocation code\n<p>\nattempts to allocate a block of one or more physical pages.\nPages are allocated in blocks which are powers of 2 in size.\nThat means that it can allocate a block 1 page, 2 pages, 4 pages and so on.\nSo long as there are enough free pages in the system to grant this request\n(nr_free_pages <font face=\"symbol\"> &gt; <\/font\n> min_free_pages) the allocation code will search the\n<tt>free_area<\/tt> for a block of pages of the size requested.\nEach element of the <tt>free_area<\/tt> has a map of the allocated and free blocks\nof pages for that sized block.\nFor example, element 2 of the array has a memory map that describes free and allocated\nblocks each of 4 pages long.\n<p>\nThe allocation algorithm first searches for blocks of pages of the size\nrequested.\nIt follows the chain of free pages that is queued on the <i>list<\/i>\nelement of the <tt>free_area<\/tt> data structure.\nIf no blocks of pages of the requested size are free, blocks of the next\nsize (which is twice that of the size requested) are looked for.\nThis process continues until all of the <tt>free_area<\/tt> has been searched or\nuntil a block of pages has been found.\nIf the block of pages found is larger than that requested it must be\nbroken down until there is a block of the right size.\nBecause the blocks are each a power of 2 pages big then this breaking\ndown process is easy as you simply break the blocks in half.\nThe free blocks are queued on the appropriate queue and the allocated\nblock of pages is returned to the caller.\n<p>\n<p>\n<img decoding=\"async\" src=\"free-area.gif\"><br \/>\nFigure: The <tt>free_area<\/tt> data structure\n<p>\n<p>For example, in the Figure above if a block of 2 pages\nwas requested, the first block of 4 pages (starting at page frame number 4) would\nbe broken into two 2 page blocks.\nThe first, starting at page frame number 4 would be returned to the caller as the\nallocated pages and the second block, starting at page frame number 6 would be queued\nas a free block of 2 pages onto element 1 of the <tt>free_area<\/tt> array.\n<p>\n<h3><\/a> Page Deallocation<\/h3>\n<p>\nAllocating blocks of pages tends to fragment memory with larger\nblocks of free pages being broken down into smaller ones.\nThe page deallocation code\n<p>\nrecombines pages into larger blocks of free pages whenever it can.\nIn fact the page block size is important as it allows for easy\ncombination of blocks into larger blocks.\n<p>\nWhenever a block of pages is freed, the adjacent or buddy block of the\nsame size is checked to see if it is free.\nIf it is, then it is combined with the newly freed block of pages to form\na new free block of pages for the next size block of pages.\nEach time two blocks of pages are recombined into a bigger block of free\npages the page deallocation code attempts to recombine that block into a yet\nlarger one.\nIn this way the blocks of free pages are as large as memory usage will allow.\n<p>\nFor example, in the  Figure above, if page frame number 1 were to be\nfreed, then that would be combined with the already free page frame number 0 and\nqueued onto element 1 of the <tt>free_area<\/tt> as a free block of size 2 pages.\n<p>\n","protected":false},"excerpt":{"rendered":"<p>Page Allocation and Deallocation There are many demands on the physical pages in the system. For example, when an image is loaded into memory the operating system needs to allocate pages. These will be freed when the image has finished &hellip; <a href=\"http:\/\/www.linux-tutorial.info\/?page_id=455\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-455","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/455","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=455"}],"version-history":[{"count":1,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/455\/revisions"}],"predecessor-version":[{"id":648,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/455\/revisions\/648"}],"wp:attachment":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=455"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}