src/stackvma-mincore.c

   1 /* Determine the virtual memory area of a given address.
   2    Copyright (C) 2006, 2008  Bruno Haible <bruno@clisp.org>
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  17
  18 /* mincore() is a system call that allows to inquire the status of a
  19    range of pages of virtual memory.  In particular, it allows to inquire
  20    whether a page is mapped at all.
  21    As of 2006, mincore() is supported by:        possible bits:
  22      - Linux,   since Linux 2.4 and glibc 2.2,   1
  23      - Solaris, since Solaris 9,                 1
  24      - MacOS X, since MacOS X 10.3 (at least),   1
  25      - FreeBSD, since FreeBSD 6.0,               MINCORE_{INCORE,REFERENCED,MODIFIED}
  26      - NetBSD,  since NetBSD 3.0 (at least),     1
  27      - OpenBSD, since OpenBSD 2.6 (at least),    1
  28    However, while the API allows to easily determine the bounds of mapped
  29    virtual memory, it does not make it easy the bounds of _unmapped_ virtual
  30    memory ranges.  We try to work around this, but it may still be slow.  */
  31
  32 #include "stackvma.h"
  33 #include <limits.h>
  34 #ifdef HAVE_UNISTD_H
  35 # include <unistd.h>
  36 #endif
  37 #include <sys/types.h>
  38 #include <sys/mman.h>
  39
  40 /* Cache for getpagesize().  */
  41 static unsigned long pagesize;
  42
  43 /* Initialize pagesize.  */
  44 static void
  45 init_pagesize (void)
  46 {
  47 #if HAVE_GETPAGESIZE
  48   pagesize = getpagesize ();
  49 #elif HAVE_SYSCONF_PAGESIZE
  50   pagesize = sysconf (_SC_PAGESIZE);
  51 #else
  52   pagesize = PAGESIZE;
  53 #endif
  54 }
  55
  56 /* Test whether the page starting at ADDR is among the address range.
  57    ADDR must be a multiple of pagesize.  */
  58 static int
  59 is_mapped (unsigned long addr)
  60 {
  61   char vec[1];
  62   return mincore ((void *) addr, pagesize, vec) >= 0;
  63 }
  64
  65 /* Assuming that the page starting at ADDR is among the address range,
  66    return the start of its virtual memory range.
  67    ADDR must be a multiple of pagesize.  */
  68 static unsigned long
  69 mapped_range_start (unsigned long addr)
  70 {
  71   /* Use a moderately sized VEC here, small enough that it fits on the stack
  72      (without requiring malloc).  */
  73   char vec[2048];
  74   unsigned long stepsize = sizeof (vec);
  75
  76   for (;;)
  77     {
  78       unsigned long max_remaining;
  79
  80       if (addr == 0)
  81         return addr;
  82
  83       max_remaining = addr / pagesize;
  84       if (stepsize > max_remaining)
  85         stepsize = max_remaining;
  86       if (mincore ((void *) (addr - stepsize * pagesize),
  87                    stepsize * pagesize, vec) < 0)
  88         /* Time to search in smaller steps.  */
  89         break;
  90       /* The entire range exists.  Continue searching in large steps.  */
  91       addr -= stepsize * pagesize;
  92     }
  93   for (;;)
  94     {
  95       unsigned long halfstepsize1;
  96       unsigned long halfstepsize2;
  97
  98       if (stepsize == 1)
  99         return addr;
 100
 101       /* Here we know that less than stepsize pages exist starting at addr.  */
 102       halfstepsize1 = (stepsize + 1) / 2;
 103       halfstepsize2 = stepsize / 2;
 104       /* halfstepsize1 + halfstepsize2 = stepsize.  */
 105
 106       if (mincore ((void *) (addr - halfstepsize1 * pagesize),
 107                    halfstepsize1 * pagesize, vec) < 0)
 108         stepsize = halfstepsize1;
 109       else
 110         {
 111           addr -= halfstepsize1 * pagesize;
 112           stepsize = halfstepsize2;
 113         }
 114     }
 115 }
 116
 117 /* Assuming that the page starting at ADDR is among the address range,
 118    return the end of its virtual memory range + 1.
 119    ADDR must be a multiple of pagesize.  */
 120 static unsigned long
 121 mapped_range_end (unsigned long addr)
 122 {
 123   /* Use a moderately sized VEC here, small enough that it fits on the stack
 124      (without requiring malloc).  */
 125   char vec[2048];
 126   unsigned long stepsize = sizeof (vec);
 127
 128   addr += pagesize;
 129   for (;;)
 130     {
 131       unsigned long max_remaining;
 132
 133       if (addr == 0) /* wrapped around? */
 134         return addr;
 135
 136       max_remaining = (- addr) / pagesize;
 137       if (stepsize > max_remaining)
 138         stepsize = max_remaining;
 139       if (mincore ((void *) addr, stepsize * pagesize, vec) < 0)
 140         /* Time to search in smaller steps.  */
 141         break;
 142       /* The entire range exists.  Continue searching in large steps.  */
 143       addr += stepsize * pagesize;
 144     }
 145   for (;;)
 146     {
 147       unsigned long halfstepsize1;
 148       unsigned long halfstepsize2;
 149
 150       if (stepsize == 1)
 151         return addr;
 152
 153       /* Here we know that less than stepsize pages exist starting at addr.  */
 154       halfstepsize1 = (stepsize + 1) / 2;
 155       halfstepsize2 = stepsize / 2;
 156       /* halfstepsize1 + halfstepsize2 = stepsize.  */
 157
 158       if (mincore ((void *) addr, halfstepsize1 * pagesize, vec) < 0)
 159         stepsize = halfstepsize1;
 160       else
 161         {
 162           addr += halfstepsize1 * pagesize;
 163           stepsize = halfstepsize2;
 164         }
 165     }
 166 }
 167
 168 /* Determine whether an address range [ADDR1..ADDR2] is completely unmapped.
 169    ADDR1 must be <= ADDR2.  */
 170 static int
 171 is_unmapped (unsigned long addr1, unsigned long addr2)
 172 {
 173   unsigned long count;
 174   unsigned long stepsize;
 175
 176   /* Round addr1 down.  */
 177   addr1 = (addr1 / pagesize) * pagesize;
 178   /* Round addr2 up and turn it into an exclusive bound.  */
 179   addr2 = ((addr2 / pagesize) + 1) * pagesize;
 180
 181   /* This is slow: mincore() does not provide a way to determine the bounds
 182      of the gaps directly.  So we have to use mincore() on individual pages
 183      over and over again.  Only after we've verified that all pages are
 184      unmapped, we know that the range is completely unmapped.
 185      If we were to traverse the pages from bottom to top or from top to bottom,
 186      it would be slow even in the average case.  To speed up the search, we
 187      exploit the fact that mapped memory ranges are larger than one page on
 188      average, therefore we have good chances of hitting a mapped area if we
 189      traverse only every second, or only fourth page, etc.  This doesn't
 190      decrease the worst-case runtime, only the average runtime.  */
 191   count = (addr2 - addr1) / pagesize;
 192   /* We have to test is_mapped (addr1 + i * pagesize) for 0 <= i < count.  */
 193   for (stepsize = 1; stepsize < count; )
 194     stepsize = 2 * stepsize;
 195   for (;;)
 196     {
 197       unsigned long addr_stepsize;
 198       unsigned long i;
 199       unsigned long addr;
 200
 201       stepsize = stepsize / 2;
 202       if (stepsize == 0)
 203         break;
 204       addr_stepsize = stepsize * pagesize;
 205       for (i = stepsize, addr = addr1 + addr_stepsize;
 206            i < count;
 207            i += 2 * stepsize, addr += 2 * addr_stepsize)
 208         /* Here addr = addr1 + i * pagesize.  */
 209         if (is_mapped (addr))
 210           return 0;
 211     }
 212   return 1;
 213 }
 214
 215 #if STACK_DIRECTION < 0
 216
 217 /* Info about the gap between this VMA and the previous one.
 218    addr must be < vma->start.  */
 219 static int
 220 mincore_is_near_this (unsigned long addr, struct vma_struct *vma)
 221 {
 222   /*   vma->start - addr <= (vma->start - vma->prev_end) / 2
 223      is mathematically equivalent to
 224        vma->prev_end <= 2 * addr - vma->start
 225      <==> is_unmapped (2 * addr - vma->start, vma->start - 1).
 226      But be careful about overflow: if 2 * addr - vma->start is negative,
 227      we consider a tiny "guard page" mapping [0, 0] to be present around
 228      NULL; it intersects the range (2 * addr - vma->start, vma->start - 1),
 229      therefore return false.  */
 230   unsigned long testaddr = addr - (vma->start - addr);
 231   if (testaddr > addr) /* overflow? */
 232     return 0;
 233   /* Here testaddr <= addr < vma->start.  */
 234   return is_unmapped (testaddr, vma->start - 1);
 235 }
 236
 237 #endif
 238 #if STACK_DIRECTION > 0
 239
 240 /* Info about the gap between this VMA and the next one.
 241    addr must be > vma->end - 1.  */
 242 static int
 243 mincore_is_near_this (unsigned long addr, struct vma_struct *vma)
 244 {
 245   /*   addr - vma->end < (vma->next_start - vma->end) / 2
 246      is mathematically equivalent to
 247        vma->next_start > 2 * addr - vma->end
 248      <==> is_unmapped (vma->end, 2 * addr - vma->end).
 249      But be careful about overflow: if 2 * addr - vma->end is > ~0UL,
 250      we consider a tiny "guard page" mapping [0, 0] to be present around
 251      NULL; it intersects the range (vma->end, 2 * addr - vma->end),
 252      therefore return false.  */
 253   unsigned long testaddr = addr + (addr - vma->end);
 254   if (testaddr < addr) /* overflow? */
 255     return 0;
 256   /* Here vma->end - 1 < addr <= testaddr.  */
 257   return is_unmapped (vma->end, testaddr);
 258 }
 259
 260 #endif
 261
 262 #ifdef STATIC
 263 STATIC
 264 #endif
 265 int
 266 sigsegv_get_vma (unsigned long address, struct vma_struct *vma)
 267 {
 268   if (pagesize == 0)
 269     init_pagesize ();
 270   address = (address / pagesize) * pagesize;
 271   vma->start = mapped_range_start (address);
 272   vma->end = mapped_range_end (address);
 273   vma->is_near_this = mincore_is_near_this;
 274   return 0;
 275 }