Physical Memory Management (mm_phys.c)

Goals

• Management of up to 64GB of physical memory using relatively small structures.
• Fast allocation of contiguous 4MB frames starting with lower memory addresses for kernel memory (malloc/free).
• Fast allocation of 4MB or 4kB frames starting with higher memory addresses for page mapping.
• Fast allocation of 4kB frames below 512MB for top level mapping pages.
• Try not to intermix these allocations as far as it is possible.
• Releasing of previously allocated frames optimized for releasing of multiple contiguous frames at once.

Large Frames Map (LFM)

• An array of 4B items, one for each 4MB frame (max. 16k of items).
• Stored in lfm global structure along with some auxiliary fields.
• Three types of an item (frame):
  • full
    one 4MB frame or 1024 4kB frames allocated
  • free
    4MB of space available
  • partially free
    
    • Divided into 4kB frames, some of them allocated.
    • Additional data structure called pfm (stands for Partially-free Frame Map) is allocated for each partially free frame. Allocation is done by PMM internal allocation function during an initialization and by malloc afterwards.
    • Pointer to a pfm structure is part of an item of the LFM. There are only 28 bits free for this pointer but it is enough because pfm structure is allocated in nonmapped address space above 0x80000000 which is at most 512MB = 2^29B large and the structure is at least word-aligned (4B). That's why 28 bits suffice. To convert 32-bit pointer to 28-bit pointer and back macros PTR_TO_WAK and WAK_TO_PTR are used (WAK stands for Word-Aligned Kernel pointer).
    • Which 4kB frames are allocated is stored in a bitmap (uchar bitmap[128])
    • To provide faster search for free frames an index of the last byte in the bitmap that contains at least one zero bit (last_free) is also part of the pfm structure.
      
• Two parts of physical memory are distinguished¹:
  • basic - below MALLOCABLE_MEMORY_4MB * 4MB
  • extended - above MALLOCABLE_MEMORY_4MB * 4MB
    
• Items of the LFM are linked into four lists:
  • f-list
    • Bidirectional sorted cyclic linked list with a head (f-head).
    • Links all free frames of basic physial memory.
    • "Sorted" means the following: T
      • The first item of the list is its head. It is on the end of the LFM array but does not represent real frame.
      • Each other item has lower index than the previous one and represents a frame with lower PFN².
  • pf-list
    • Unidirectional sorted cyclic linked list with a head (pf-head)
    • Links all partially free frames of basic physial memory.
    • "Sorted" has exactly the same meaning as in a context of f-list.
    • Unlike f-list pf-list linking is indirect, i.e. the "next" index is placed into pfm structure because of lack of space in an item of the LFM array.
  • xf-list³
    • Bidirectional unsorted cyclic linked list with a head (xf-head)
    • The same characteristics as f-list except for frames that are linked with this list. They are all free frames in extended physical memory.
  • xpf-list³
    • Unidirectional unsorted cyclic linked list with a head (xpf-head)
    • The same characteristics as pf-list except for frames that are linked with this list. They are all partially free frames in extended physical memory.
  
  
  
  
  
  
  
  
  Immediately after initialization (by init_phys)

Thread safety

• All exported functions are thread-safe except for these with "_unsafe" suffix.
• The lfm is the only global data structure which is updated after the initialization is over.
• It is protected by the semaphore shared with malloc (rwlock may be an optimization because some functions don't modify any global structure).
• That's why kernel memory allocation and frames allocation are mutually excluded operations as well as multiple concurrent frames allocations.
• The reason for this behavior is that malloc sometimes needs to allocate a frame and also PMM⁵ sometimes needs to allocate a pfm structure by malloc.

Frames Allocation

• Memory for kernel is allocated by function pmm_allocate_kernel_frames_unsafe which allocates specified number of contiguous frames searching them from the end of the f-list.
• Other allocations are done by mm_allocate_frames function and its derivatives:
  • Allocation of specified number of 4kB or 4MB frames.
  • 4MB frames:
    • A block⁴ of contiguous frames will be allocated.
    • The first item of the f-list will be the last frame in the block.
    • Adds items of the f-list from its beginning to the block until required count is reached or it is not possible to allocate next contiguous frame.
    • Function returns PFN of the first frame of the block (the one with the lowest PFN).
  • 4kB frames:
    • pf-list not empty => allocates the block as large as it is possible or needed from the first pf-frame in pf-list.
    • Blocks don't overflow from one pf-frame to another. Block is ended even if the next pf-frame and the previous one are contiguous and is theoretically possible to extend the block to the next pf-frame keeping it contiguous.
    • If the pf-lists is empty and more frames are required than f-frames are processed.
    • Converts f-frames to full frames with 4kB granularity while there are at least 1024 requested frames and f-frames are contiguous.
    • Processing of each f-frame will add 1024 frames to the block.
    • For remaining requested frames (less than 1024) one f-frame is converted to pf-frame and block of frames is allocated there.
  • If there is not enough memory to allocate required number of frames than kernel memory manager is asked for releasing some of its unused frames. There may be some frames previously allocated but now unused. If no memory is returned PFN_INVALID constant is returned by frame allocation function.
  • If there is some exteneded memory part previously described algorithm will allocate extended frames (using the xf-list and the xpf-list) at first.³
• There are four functions provided for allocation (parameters description can be found in source code comments):
  • mm_alllocate_frame - allocates one frame of specified size
  • mm_allocate_frames - allocates at most specified count of frames of specidied size
  • mm_allocate_frames_with_check - check free frames count and allocates only if there is enough free memory to complete allocation, it can be specified wheather to ask kernel memory manager to release its unused memory or not by additional parameter
  • mm_allocate_frames_below512M - allocates frames only from the f-list or pf-list, this frames are guaranteed to be placed in the first 512MB of physical memory.

Frames Releasing

• Frames allocated for kernel memory (i.e. by malloc) are released only when there is a lack of memory for page mapping.
  • Kernel memory manager frees frames only by explicit request of PMM.
  • If there is not enough memory for frames allocation PMM calls kmm_free_frames and this function may release some frames by pmm_free_kernel_frames_unsafe function.
• Frames are released by mm_free_contiguous_frames function.
  • A closed interval of PFNs and a size of freed frames are specified.
  • It is an error to release frames that were not allocated (warning: no check is performed because such test would cut performance down).
  • All transitions which can occure by releasing frames are handled (pf-frame to f-frame, pf-frame to pf-frame, full-frame to f-frame, full-frame to pf-frame)
  • New f-frames or pf-frames may be generated so some operations over lists may be needed.
  • Generated frames have to be merged into appropriate list unless they are in extended memory part.
  • Function implements lazy approach for merging.
  • Because only a block of contiguous frames can be released by one call of this function a search fo predecessor of newly inserted items is needed in each call of the function.
  • Optimization: if a caller releases many (partially) sorted contiguous blocks of frames it may take advantage of the last two parameters of the function.
  • Caller may specify where to start searching (in which item of the f-list and the pf-list).
  • It is not necessary to specify these parameters - default starting points are heads of lists.
  • It is also not necessary to free frames which PFNs are less than these parameters - the f-list can be searched in both directions and if unidirection of the pf-list prevents merging it starts from the pf-head.
  • Extended frames are simply added on the end of the xf-list or beginning of the xpf-list. Of course, no merging is needed because extended lists are not sorted.³

Memory Querying

• mm_get_free_frames_count - returns the number of free frames of specified size with possibility of counting also releasable kernel memory frames
• mm_get_physical_memory_size_4kb - gets size of whole physical memory in multiples of 4kB