servers/vm/alloc.c

   1 /* This file is concerned with allocating and freeing arbitrary-size blocks of
   2  * physical memory.
   3  */
   4
   5 #define _SYSTEM 1
   6
   7 #include <minix/com.h>
   8 #include <minix/callnr.h>
   9 #include <minix/type.h>
  10 #include <minix/config.h>
  11 #include <minix/const.h>
  12 #include <minix/sysutil.h>
  13 #include <minix/syslib.h>
  14 #include <minix/debug.h>
  15 #include <minix/bitmap.h>
  16
  17 #include <sys/mman.h>
  18
  19 #include <limits.h>
  20 #include <string.h>
  21 #include <errno.h>
  22 #include <assert.h>
  23 #include <memory.h>
  24
  25 #include "vm.h"
  26 #include "proto.h"
  27 #include "util.h"
  28 #include "glo.h"
  29 #include "sanitycheck.h"
  30 #include "memlist.h"
  31
  32 /* Number of physical pages in a 32-bit address space */
  33 #define NUMBER_PHYSICAL_PAGES (0x100000000ULL/VM_PAGE_SIZE)
  34 #define PAGE_BITMAP_CHUNKS BITMAP_CHUNKS(NUMBER_PHYSICAL_PAGES)
  35 static bitchunk_t free_pages_bitmap[PAGE_BITMAP_CHUNKS];
  36 #define PAGE_CACHE_MAX 10000
  37 static int free_page_cache[PAGE_CACHE_MAX];
  38 static int free_page_cache_size = 0;
  39
  40 /* Used for sanity check. */
  41 static phys_bytes mem_low, mem_high;
  42
  43 static void free_pages(phys_bytes addr, int pages);
  44 static phys_bytes alloc_pages(int pages, int flags);
  45
  46 #if SANITYCHECKS
  47 struct {
  48         int used;
  49         char *file;
  50         int line;
  51 } pagemap[NUMBER_PHYSICAL_PAGES];
  52 #endif
  53
  54 #define page_isfree(i) GET_BIT(free_pages_bitmap, i)
  55
  56 /*===========================================================================*
  57  *                              alloc_mem                                    *
  58  *===========================================================================*/
  59 phys_clicks alloc_mem(phys_clicks clicks, u32_t memflags)
  60 {
  61 /* Allocate a block of memory from the free list using first fit. The block
  62  * consists of a sequence of contiguous bytes, whose length in clicks is
  63  * given by 'clicks'.  A pointer to the block is returned.  The block is
  64  * always on a click boundary.  This procedure is called when memory is
  65  * needed for FORK or EXEC.
  66  */
  67   phys_clicks mem = NO_MEM, align_clicks = 0;
  68
  69   if(memflags & PAF_ALIGN64K) {
  70         align_clicks = (64 * 1024) / CLICK_SIZE;
  71         clicks += align_clicks;
  72   } else if(memflags & PAF_ALIGN16K) {
  73         align_clicks = (16 * 1024) / CLICK_SIZE;
  74         clicks += align_clicks;
  75   }
  76
  77   mem = alloc_pages(clicks, memflags);
  78   if(mem == NO_MEM) {
  79     free_yielded(clicks * CLICK_SIZE);
  80     mem = alloc_pages(clicks, memflags);
  81   }
  82
  83   if(mem == NO_MEM)
  84         return mem;
  85
  86   if(align_clicks) {
  87         phys_clicks o;
  88         o = mem % align_clicks;
  89         if(o > 0) {
  90                 phys_clicks e;
  91                 e = align_clicks - o;
  92                 free_mem(mem, e);
  93                 mem += e;
  94         }
  95   }
  96
  97   return mem;
  98 }
  99
 100 /*===========================================================================*
 101  *                              free_mem                                     *
 102  *===========================================================================*/
 103 void free_mem(phys_clicks base, phys_clicks clicks)
 104 {
 105 /* Return a block of free memory to the hole list.  The parameters tell where
 106  * the block starts in physical memory and how big it is.  The block is added
 107  * to the hole list.  If it is contiguous with an existing hole on either end,
 108  * it is merged with the hole or holes.
 109  */
 110   if (clicks == 0) return;
 111
 112   assert(CLICK_SIZE == VM_PAGE_SIZE);
 113   free_pages(base, clicks);
 114   return;
 115 }
 116
 117 /*===========================================================================*
 118  *                              mem_init                                     *
 119  *===========================================================================*/
 120 void mem_init(chunks)
 121 struct memory *chunks;          /* list of free memory chunks */
 122 {
 123 /* Initialize hole lists.  There are two lists: 'hole_head' points to a linked
 124  * list of all the holes (unused memory) in the system; 'free_slots' points to
 125  * a linked list of table entries that are not in use.  Initially, the former
 126  * list has one entry for each chunk of physical memory, and the second
 127  * list links together the remaining table slots.  As memory becomes more
 128  * fragmented in the course of time (i.e., the initial big holes break up into
 129  * smaller holes), new table slots are needed to represent them.  These slots
 130  * are taken from the list headed by 'free_slots'.
 131  */
 132   int i, first = 0;
 133
 134   total_pages = 0;
 135
 136   memset(free_pages_bitmap, 0, sizeof(free_pages_bitmap));
 137
 138   /* Use the chunks of physical memory to allocate holes. */
 139   for (i=NR_MEMS-1; i>=0; i--) {
 140         if (chunks[i].size > 0) {
 141                 phys_bytes from = CLICK2ABS(chunks[i].base),
 142                         to = CLICK2ABS(chunks[i].base+chunks[i].size)-1;
 143                 if(first || from < mem_low) mem_low = from;
 144                 if(first || to > mem_high) mem_high = to;
 145                 free_mem(chunks[i].base, chunks[i].size);
 146                 total_pages += chunks[i].size;
 147                 first = 0;
 148         }
 149   }
 150 }
 151
 152 #if SANITYCHECKS
 153 void mem_sanitycheck(char *file, int line)
 154 {
 155         int i;
 156         for(i = 0; i < NUMBER_PHYSICAL_PAGES; i++) {
 157                 if(!page_isfree(i)) continue;
 158                 MYASSERT(usedpages_add(i * VM_PAGE_SIZE, VM_PAGE_SIZE) == OK);
 159         }
 160 }
 161 #endif
 162
 163 void memstats(int *nodes, int *pages, int *largest)
 164 {
 165         int i;
 166         *nodes = 0;
 167         *pages = 0;
 168         *largest = 0;
 169
 170         for(i = 0; i < NUMBER_PHYSICAL_PAGES; i++) {
 171                 int size = 0;
 172                 while(i < NUMBER_PHYSICAL_PAGES && page_isfree(i)) {
 173                         size++;
 174                         i++;
 175                 }
 176                 if(size == 0) continue;
 177                 (*nodes)++;
 178                 (*pages)+= size;
 179                 if(size > *largest)
 180                         *largest = size;
 181         }
 182 }
 183
 184 static int findbit(int low, int startscan, int pages, int memflags, int *len)
 185 {
 186         int run_length = 0, i;
 187         int freerange_start = startscan;
 188
 189         for(i = startscan; i >= low; i--) {
 190                 if(!page_isfree(i)) {
 191                         int pi;
 192                         int chunk = i/BITCHUNK_BITS, moved = 0;
 193                         run_length = 0;
 194                         pi = i;
 195                         while(chunk > 0 &&
 196                            !MAP_CHUNK(free_pages_bitmap, chunk*BITCHUNK_BITS)) {
 197                                 chunk--;
 198                                 moved = 1;
 199                         }
 200                         if(moved) { i = chunk * BITCHUNK_BITS + BITCHUNK_BITS; }
 201                         continue;
 202                 }
 203                 if(!run_length) { freerange_start = i; run_length = 1; }
 204                 else { freerange_start--; run_length++; }
 205                 assert(run_length <= pages);
 206                 if(run_length == pages) {
 207                         /* good block found! */
 208                         *len = run_length;
 209                         return freerange_start;
 210                 }
 211         }
 212
 213         return NO_MEM;
 214 }
 215
 216 /*===========================================================================*
 217  *                              alloc_pages                                  *
 218  *===========================================================================*/
 219 static phys_bytes alloc_pages(int pages, int memflags)
 220 {
 221         phys_bytes boundary16 = 16 * 1024 * 1024 / VM_PAGE_SIZE;
 222         phys_bytes boundary1  =  1 * 1024 * 1024 / VM_PAGE_SIZE;
 223         phys_bytes mem = NO_MEM;
 224         int maxpage = NUMBER_PHYSICAL_PAGES - 1, i;
 225         static int lastscan = -1;
 226         int startscan, run_length;
 227
 228         if(memflags & PAF_LOWER16MB)
 229                 maxpage = boundary16 - 1;
 230         else if(memflags & PAF_LOWER1MB)
 231                 maxpage = boundary1 - 1;
 232         else {
 233                 /* no position restrictions: check page cache */
 234                 if(pages == 1) {
 235                         while(free_page_cache_size > 0) {
 236                                 i = free_page_cache[free_page_cache_size-1];
 237                                 if(page_isfree(i)) {
 238                                         free_page_cache_size--;
 239                                         mem = i;
 240                                         assert(mem != NO_MEM);
 241                                         run_length = 1;
 242                                         break;
 243                                 }
 244                                 free_page_cache_size--;
 245                         }
 246                 }
 247         }
 248
 249         if(lastscan < maxpage && lastscan >= 0)
 250                 startscan = lastscan;
 251         else    startscan = maxpage;
 252
 253         if(mem == NO_MEM)
 254                 mem = findbit(0, startscan, pages, memflags, &run_length);
 255         if(mem == NO_MEM)
 256                 mem = findbit(0, maxpage, pages, memflags, &run_length);
 257         if(mem == NO_MEM)
 258                 return NO_MEM;
 259
 260         /* remember for next time */
 261         lastscan = mem;
 262
 263         for(i = mem; i < mem + pages; i++) {
 264                 UNSET_BIT(free_pages_bitmap, i);
 265         }
 266
 267         if(memflags & PAF_CLEAR) {
 268                 int s;
 269                 if ((s= sys_memset(NONE, 0, CLICK_SIZE*mem,
 270                         VM_PAGE_SIZE*pages)) != OK)
 271                         panic("alloc_mem: sys_memset failed: %d", s);
 272         }
 273
 274         return mem;
 275 }
 276
 277 /*===========================================================================*
 278  *                              free_pages                                   *
 279  *===========================================================================*/
 280 static void free_pages(phys_bytes pageno, int npages)
 281 {
 282         int i, lim = pageno + npages - 1;
 283
 284 #if JUNKFREE
 285        if(sys_memset(NONE, 0xa5a5a5a5, VM_PAGE_SIZE * pageno,
 286                VM_PAGE_SIZE * npages) != OK)
 287                        panic("free_pages: sys_memset failed");
 288 #endif
 289
 290         for(i = pageno; i <= lim; i++) {
 291                 SET_BIT(free_pages_bitmap, i);
 292                 if(free_page_cache_size < PAGE_CACHE_MAX) {
 293                         free_page_cache[free_page_cache_size++] = i;
 294                 }
 295         }
 296 }
 297
 298 /*===========================================================================*
 299  *                              printmemstats                                *
 300  *===========================================================================*/
 301 void printmemstats(void)
 302 {
 303         int nodes, pages, largest;
 304         memstats(&nodes, &pages, &largest);
 305         printf("%d blocks, %d pages (%lukB) free, largest %d pages (%lukB)\n",
 306                 nodes, pages, (unsigned long) pages * (VM_PAGE_SIZE/1024),
 307                 largest, (unsigned long) largest * (VM_PAGE_SIZE/1024));
 308 }
 309
 310
 311 #if SANITYCHECKS
 312
 313 /*===========================================================================*
 314  *                              usedpages_reset                              *
 315  *===========================================================================*/
 316 void usedpages_reset(void)
 317 {
 318         memset(pagemap, 0, sizeof(pagemap));
 319 }
 320
 321 /*===========================================================================*
 322  *                              usedpages_add                                *
 323  *===========================================================================*/
 324 int usedpages_add_f(phys_bytes addr, phys_bytes len, char *file, int line)
 325 {
 326         u32_t pagestart, pages;
 327
 328         if(!incheck)
 329                 return OK;
 330
 331         assert(!(addr % VM_PAGE_SIZE));
 332         assert(!(len % VM_PAGE_SIZE));
 333         assert(len > 0);
 334
 335         pagestart = addr / VM_PAGE_SIZE;
 336         pages = len / VM_PAGE_SIZE;
 337
 338         while(pages > 0) {
 339                 phys_bytes thisaddr;
 340                 assert(pagestart > 0);
 341                 assert(pagestart < NUMBER_PHYSICAL_PAGES);
 342                 thisaddr = pagestart * VM_PAGE_SIZE;
 343                 assert(pagestart >= 0);
 344                 assert(pagestart < NUMBER_PHYSICAL_PAGES);
 345                 if(pagemap[pagestart].used) {
 346                         static int warnings = 0;
 347                         if(warnings++ < 100)
 348                                 printf("%s:%d: usedpages_add: addr 0x%lx reused, first %s:%d\n",
 349                                         file, line, thisaddr, pagemap[pagestart].file, pagemap[pagestart].line);
 350                         util_stacktrace();
 351                         return EFAULT;
 352                 }
 353                 pagemap[pagestart].used = 1;
 354                 pagemap[pagestart].file = file;
 355                 pagemap[pagestart].line = line;
 356                 pages--;
 357                 pagestart++;
 358         }
 359
 360         return OK;
 361 }
 362
 363 #endif
 364