src/stackvma-mincore.c

   1 /* Determine the virtual memory area of a given address.
   2    Copyright (C) 2006, 2008-2010  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 /* The glibc declaration of mincore() uses 'unsigned char *', whereas the BSD
  41    declaration uses 'char *'.  */
  42 #if __GLIBC__ >= 2
  43 typedef unsigned char pageinfo_t;
  44 #else
  45 typedef char pageinfo_t;
  46 #endif
  47
  48 /* Cache for getpagesize().  */
  49 static unsigned long pagesize;
  50
  51 /* Initialize pagesize.  */
  52 static void
  53 init_pagesize (void)
  54 {
  55 #if HAVE_GETPAGESIZE
  56   pagesize = getpagesize ();
  57 #elif HAVE_SYSCONF_PAGESIZE
  58   pagesize = sysconf (_SC_PAGESIZE);
  59 #else
  60   pagesize = PAGESIZE;
  61 #endif
  62 }
  63
  64 /* Test whether the page starting at ADDR is among the address range.
  65    ADDR must be a multiple of pagesize.  */
  66 static int
  67 is_mapped (unsigned long addr)
  68 {
  69   pageinfo_t vec[1];
  70   return mincore ((void *) addr, pagesize, vec) >= 0;
  71 }
  72
  73 /* Assuming that the page starting at ADDR is among the address range,
  74    return the start of its virtual memory range.
  75    ADDR must be a multiple of pagesize.  */
  76 static unsigned long
  77 mapped_range_start (unsigned long addr)
  78 {
  79   /* Use a moderately sized VEC here, small enough that it fits on the stack
  80      (without requiring malloc).  */
  81   pageinfo_t vec[1024];
  82   unsigned long stepsize = sizeof (vec);
  83
  84   for (;;)
  85     {
  86       unsigned long max_remaining;
  87
  88       if (addr == 0)
  89         return addr;
  90
  91       max_remaining = addr / pagesize;
  92       if (stepsize > max_remaining)
  93         stepsize = max_remaining;
  94       if (mincore ((void *) (addr - stepsize * pagesize),
  95                    stepsize * pagesize, vec) < 0)
  96         /* Time to search in smaller steps.  */
  97         break;
  98       /* The entire range exists.  Continue searching in large steps.  */
  99       addr -= stepsize * pagesize;
 100     }
 101   for (;;)
 102     {
 103       unsigned long halfstepsize1;
 104       unsigned long halfstepsize2;
 105
 106       if (stepsize == 1)
 107         return addr;
 108
 109       /* Here we know that less than stepsize pages exist starting at addr.  */
 110       halfstepsize1 = (stepsize + 1) / 2;
 111       halfstepsize2 = stepsize / 2;
 112       /* halfstepsize1 + halfstepsize2 = stepsize.  */
 113
 114       if (mincore ((void *) (addr - halfstepsize1 * pagesize),
 115                    halfstepsize1 * pagesize, vec) < 0)
 116         stepsize = halfstepsize1;
 117       else
 118         {
 119           addr -= halfstepsize1 * pagesize;
 120           stepsize = halfstepsize2;
 121         }
 122     }
 123 }
 124
 125 /* Assuming that the page starting at ADDR is among the address range,
 126    return the end of its virtual memory range + 1.
 127    ADDR must be a multiple of pagesize.  */
 128 static unsigned long
 129 mapped_range_end (unsigned long addr)
 130 {
 131   /* Use a moderately sized VEC here, small enough that it fits on the stack
 132      (without requiring malloc).  */
 133   pageinfo_t vec[1024];
 134   unsigned long stepsize = sizeof (vec);
 135
 136   addr += pagesize;
 137   for (;;)
 138     {
 139       unsigned long max_remaining;
 140
 141       if (addr == 0) /* wrapped around? */
 142         return addr;
 143
 144       max_remaining = (- addr) / pagesize;
 145       if (stepsize > max_remaining)
 146         stepsize = max_remaining;
 147       if (mincore ((void *) addr, stepsize * pagesize, vec) < 0)
 148         /* Time to search in smaller steps.  */
 149         break;
 150       /* The entire range exists.  Continue searching in large steps.  */
 151       addr += stepsize * pagesize;
 152     }
 153   for (;;)
 154     {
 155       unsigned long halfstepsize1;
 156       unsigned long halfstepsize2;
 157
 158       if (stepsize == 1)
 159         return addr;
 160
 161       /* Here we know that less than stepsize pages exist starting at addr.  */
 162       halfstepsize1 = (stepsize + 1) / 2;
 163       halfstepsize2 = stepsize / 2;
 164       /* halfstepsize1 + halfstepsize2 = stepsize.  */
 165
 166       if (mincore ((void *) addr, halfstepsize1 * pagesize, vec) < 0)
 167         stepsize = halfstepsize1;
 168       else
 169         {
 170           addr += halfstepsize1 * pagesize;
 171           stepsize = halfstepsize2;
 172         }
 173     }
 174 }
 175
 176 /* Determine whether an address range [ADDR1..ADDR2] is completely unmapped.
 177    ADDR1 must be <= ADDR2.  */
 178 static int
 179 is_unmapped (unsigned long addr1, unsigned long addr2)
 180 {
 181   unsigned long count;
 182   unsigned long stepsize;
 183
 184   /* Round addr1 down.  */
 185   addr1 = (addr1 / pagesize) * pagesize;
 186   /* Round addr2 up and turn it into an exclusive bound.  */
 187   addr2 = ((addr2 / pagesize) + 1) * pagesize;
 188
 189   /* This is slow: mincore() does not provide a way to determine the bounds
 190      of the gaps directly.  So we have to use mincore() on individual pages
 191      over and over again.  Only after we've verified that all pages are
 192      unmapped, we know that the range is completely unmapped.
 193      If we were to traverse the pages from bottom to top or from top to bottom,
 194      it would be slow even in the average case.  To speed up the search, we
 195      exploit the fact that mapped memory ranges are larger than one page on
 196      average, therefore we have good chances of hitting a mapped area if we
 197      traverse only every second, or only fourth page, etc.  This doesn't
 198      decrease the worst-case runtime, only the average runtime.  */
 199   count = (addr2 - addr1) / pagesize;
 200   /* We have to test is_mapped (addr1 + i * pagesize) for 0 <= i < count.  */
 201   for (stepsize = 1; stepsize < count; )
 202     stepsize = 2 * stepsize;
 203   for (;;)
 204     {
 205       unsigned long addr_stepsize;
 206       unsigned long i;
 207       unsigned long addr;
 208
 209       stepsize = stepsize / 2;
 210       if (stepsize == 0)
 211         break;
 212       addr_stepsize = stepsize * pagesize;
 213       for (i = stepsize, addr = addr1 + addr_stepsize;
 214            i < count;
 215            i += 2 * stepsize, addr += 2 * addr_stepsize)
 216         /* Here addr = addr1 + i * pagesize.  */
 217         if (is_mapped (addr))
 218           return 0;
 219     }
 220   return 1;
 221 }
 222
 223 #if STACK_DIRECTION < 0
 224
 225 /* Info about the gap between this VMA and the previous one.
 226    addr must be < vma->start.  */
 227 static int
 228 mincore_is_near_this (unsigned long addr, struct vma_struct *vma)
 229 {
 230   /*   vma->start - addr <= (vma->start - vma->prev_end) / 2
 231      is mathematically equivalent to
 232        vma->prev_end <= 2 * addr - vma->start
 233      <==> is_unmapped (2 * addr - vma->start, vma->start - 1).
 234      But be careful about overflow: if 2 * addr - vma->start is negative,
 235      we consider a tiny "guard page" mapping [0, 0] to be present around
 236      NULL; it intersects the range (2 * addr - vma->start, vma->start - 1),
 237      therefore return false.  */
 238   unsigned long testaddr = addr - (vma->start - addr);
 239   if (testaddr > addr) /* overflow? */
 240     return 0;
 241   /* Here testaddr <= addr < vma->start.  */
 242   return is_unmapped (testaddr, vma->start - 1);
 243 }
 244
 245 #endif
 246 #if STACK_DIRECTION > 0
 247
 248 /* Info about the gap between this VMA and the next one.
 249    addr must be > vma->end - 1.  */
 250 static int
 251 mincore_is_near_this (unsigned long addr, struct vma_struct *vma)
 252 {
 253   /*   addr - vma->end < (vma->next_start - vma->end) / 2
 254      is mathematically equivalent to
 255        vma->next_start > 2 * addr - vma->end
 256      <==> is_unmapped (vma->end, 2 * addr - vma->end).
 257      But be careful about overflow: if 2 * addr - vma->end is > ~0UL,
 258      we consider a tiny "guard page" mapping [0, 0] to be present around
 259      NULL; it intersects the range (vma->end, 2 * addr - vma->end),
 260      therefore return false.  */
 261   unsigned long testaddr = addr + (addr - vma->end);
 262   if (testaddr < addr) /* overflow? */
 263     return 0;
 264   /* Here vma->end - 1 < addr <= testaddr.  */
 265   return is_unmapped (vma->end, testaddr);
 266 }
 267
 268 #endif
 269
 270 #ifdef STATIC
 271 STATIC
 272 #endif
 273 int
 274 sigsegv_get_vma (unsigned long address, struct vma_struct *vma)
 275 {
 276   if (pagesize == 0)
 277     init_pagesize ();
 278   address = (address / pagesize) * pagesize;
 279   vma->start = mapped_range_start (address);
 280   vma->end = mapped_range_end (address);
 281   vma->is_near_this = mincore_is_near_this;
 282   return 0;
 283 }