reactos/ntoskrnl/mm/freelist.c

   1 /*
   2  * COPYRIGHT:    See COPYING in the top level directory
   3  * PROJECT:      ReactOS kernel
   4  * FILE:         ntoskrnl/mm/freelist.c
   5  * PURPOSE:      Handle the list of free physical pages
   6  * PROGRAMMER:   David Welch (welch@mcmail.com)
   7  * UPDATE HISTORY:
   8  *               27/05/98: Created
   9  *               18/08/98: Added a fix from Robert Bergkvist
  10  */
  11
  12 /*
  13  * NOTE: The list of free pages is implemented as an unsorted double linked
  14  * list. This should make added or removing pages fast when you don't care
  15  * about the physical address. Because the entirety of physical memory is
  16  * mapped from 0xd0000000 upwards it is easy to do a mapping between
  17  * physical and linear address.
  18  */
  19
  20 /* INCLUDES ****************************************************************/
  21
  22 #include <internal/stddef.h>
  23 #include <internal/hal/page.h>
  24 #include <internal/mm.h>
  25 #include <internal/ntoskrnl.h>
  26 #include <internal/bitops.h>
  27 #include <ddk/ntddk.h>
  28
  29 #define NDEBUG
  30 #include <internal/debug.h>
  31
  32 /* TYPES *******************************************************************/
  33
  34 typedef struct _free_page
  35 /*
  36  * PURPOSE: At the start of every region of free physical pages
  37  */
  38 {
  39         struct _free_page* next;
  40         struct _free_page* previous;
  41         unsigned int nr_pages;
  42 } free_page_hdr;
  43
  44 /* GLOBALS ****************************************************************/
  45
  46 /*
  47  * PURPOSE: Points to the first page in the free list
  48  */
  49 free_page_hdr* free_page_list_head=NULL;
  50
  51 /* FUNCTIONS *************************************************************/
  52
  53 void free_page(unsigned int physical_base, unsigned int nr)
  54 /*
  55  * FUNCTION: Add a physically continuous range of pages to the free list
  56  * ARGUMENTS:
  57  *         physical_base = The first physical address to free
  58  *         nr = the size of the region (in pages) to free
  59  * NOTES: This function attempts to keep the list partially unfragmented
  60  */
  61 {
  62    unsigned int eflags;
  63    free_page_hdr* hdr=NULL;
  64
  65    DPRINT("Freeing %x to %x\n",physical_base,physical_base
  66           + (nr*PAGESIZE));
  67
  68    /*
  69     * This must be atomic
  70     */
  71    __asm__("pushf\n\tpop %0\n\tcli\n\t"
  72            : "=d" (eflags));
  73
  74    /*
  75     *
  76     */
  77    hdr = (free_page_hdr *)physical_to_linear(physical_base);
  78
  79    DPRINT("free_page_hdr %x\n",hdr);
  80    DPRINT("free_page_list_head %x\n",free_page_list_head);
  81
  82    if (free_page_list_head!=NULL)
  83      {
  84         free_page_list_head->previous=hdr;
  85      }
  86    hdr->next=free_page_list_head;
  87    hdr->previous=NULL;
  88    hdr->nr_pages = nr;
  89    free_page_list_head=hdr;
  90
  91    __asm__("push %0\n\tpopf\n\t"
  92            :
  93            : "d" (eflags));
  94 }
  95
  96 unsigned int get_dma_page(unsigned int max_address)
  97 /*
  98  * FUNCTION: Gets a page with a restricted max physical address (i.e.
  99  * suitable for dma)
 100  * ARGUMENTS:
 101  *         max_address = The maximum address usable by the caller
 102  * RETURNS:
 103  *      The physical address of the page if it succeeds
 104  *      NULL if it fails.
 105  * NOTES: This is very inefficent because the list isn't sorted. On the
 106  * other hand sorting the list would be quite expensive especially if dma
 107  * is only used infrequently. Perhaps a special cache of dma pages should
 108  * be maintained?
 109  */
 110 {
 111    free_page_hdr* current=NULL;
 112
 113    if (free_page_list_head==NULL)
 114      {
 115         printk("CRITICAL: Unable to allocate page\n");
 116         KeBugCheck(KBUG_OUT_OF_MEMORY);
 117      }
 118
 119    /*
 120     * Walk the free page list looking for suitable memory
 121     */
 122    current = free_page_list_head;
 123    while (current!=NULL)
 124      {
 125         if ( ((int)current) < max_address)
 126           {
 127              /*
 128               * We take the first page from the region
 129               */
 130              free_page_hdr* nhdr = (free_page_hdr *)(((int)current)+PAGESIZE);
 131              if (current->previous!=NULL)
 132                {
 133                   current->previous->next=nhdr;
 134                }
 135              if (current->next!=NULL)
 136                {
 137                   current->next->previous=nhdr;
 138                }
 139              nhdr->next=current->next;
 140              nhdr->previous=current->previous;
 141              nhdr->nr_pages=current->nr_pages-1;
 142              if (free_page_list_head==current)
 143                {
 144                   free_page_list_head=nhdr;
 145                }
 146
 147              return ((int)current);
 148           }
 149
 150         current=current->next;
 151      }
 152    return(NULL);
 153 }
 154
 155 unsigned int get_free_page(void)
 156 /*
 157  * FUNCTION: Allocates a page
 158  * RETURNS: The physical address of the page allocated
 159  */
 160 {
 161    unsigned int addr;
 162
 163    /*
 164     * This must be atomic wrt everything
 165     */
 166    unsigned int eflags;
 167    __asm__("pushf\n\tpop %0\n\tcli\n\t"
 168            : "=d" (eflags));
 169    CHECKPOINT;
 170    /*
 171     * If we are totally out of memory then panic
 172     */
 173    if (free_page_list_head==NULL)
 174      {
 175         printk("CRITICAL: Unable to allocate page\n");
 176         KeBugCheck(KBUG_OUT_OF_MEMORY);
 177      }
 178    CHECKPOINT;
 179    addr = 0;
 180    CHECKPOINT;
 181    if (free_page_list_head->nr_pages>1)
 182      {
 183         free_page_list_head->nr_pages--;
 184         addr = ((unsigned int)free_page_list_head) +
 185           (free_page_list_head->nr_pages * PAGESIZE);
 186      }
 187    else
 188      {
 189         addr = (unsigned int)free_page_list_head;
 190         free_page_list_head = free_page_list_head -> next;
 191      }
 192    CHECKPOINT;
 193    __asm__("push %0\n\tpopf\n\t"
 194            :
 195            : "d" (eflags));
 196
 197    addr = addr - (IDMAP_BASE);
 198    DPRINT("allocated %x\n",addr);
 199    CHECKPOINT;
 200    return(addr);
 201 }
 202
 203
 204
 205