src/extent-scan.c

   1 /* extent-scan.c -- core functions for scanning extents
   2    Copyright (C) 2010-2012 Free Software Foundation, Inc.
   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 3 of the License, or
   7    (at your option) 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, see <http://www.gnu.org/licenses/>.
  16
  17    Written by Jie Liu (jeff.liu@oracle.com).  */
  18
  19 #include <config.h>
  20 #include <sys/types.h>
  21 #include <sys/ioctl.h>
  22 #include <sys/utsname.h>
  23 #include <assert.h>
  24
  25 #include "system.h"
  26 #include "extent-scan.h"
  27 #include "fiemap.h"
  28 #include "xstrtol.h"
  29
  30
  31 /* Work around Linux kernel issues on BTRFS and EXT4 before 2.6.39.
  32    FIXME: remove in 2013, or whenever we're pretty confident
  33    that the offending, unpatched kernels are no longer in use.  */
  34 static bool
  35 extent_need_sync (void)
  36 {
  37   /* For now always return true, to be on the safe side.
  38      If/when FIEMAP semantics are well defined (before SEEK_HOLE support
  39      is usable) and kernels implementing them are in use, we may relax
  40      this once again.  */
  41   return true;
  42
  43 #if FIEMAP_BEHAVIOR_IS_DEFINED_AND_USABLE
  44   static int need_sync = -1;
  45
  46   if (need_sync == -1)
  47     {
  48       struct utsname name;
  49       need_sync = 0; /* No workaround by default.  */
  50
  51 # ifdef __linux__
  52       if (uname (&name) != -1 && STRNCMP_LIT (name.release, "2.6.") == 0)
  53         {
  54            unsigned long val;
  55            if (xstrtoul (name.release + 4, NULL, 10, &val, NULL) == LONGINT_OK)
  56              {
  57                if (val < 39)
  58                  need_sync = 1;
  59              }
  60         }
  61 # endif
  62     }
  63
  64   return need_sync;
  65 #endif
  66 }
  67
  68 /* Allocate space for struct extent_scan, initialize the entries if
  69    necessary and return it as the input argument of extent_scan_read().  */
  70 extern void
  71 extent_scan_init (int src_fd, struct extent_scan *scan)
  72 {
  73   scan->fd = src_fd;
  74   scan->ei_count = 0;
  75   scan->ext_info = NULL;
  76   scan->scan_start = 0;
  77   scan->initial_scan_failed = false;
  78   scan->hit_final_extent = false;
  79   scan->fm_flags = extent_need_sync () ? FIEMAP_FLAG_SYNC : 0;
  80 }
  81
  82 #ifdef __linux__
  83 # ifndef FS_IOC_FIEMAP
  84 #  define FS_IOC_FIEMAP _IOWR ('f', 11, struct fiemap)
  85 # endif
  86 /* Call ioctl(2) with FS_IOC_FIEMAP (available in linux 2.6.27) to
  87    obtain a map of file extents excluding holes.  */
  88 extern bool
  89 extent_scan_read (struct extent_scan *scan)
  90 {
  91   unsigned int si = 0;
  92   struct extent_info *last_ei IF_LINT ( = scan->ext_info);
  93
  94   while (true)
  95     {
  96       union { struct fiemap f; char c[4096]; } fiemap_buf;
  97       struct fiemap *fiemap = &fiemap_buf.f;
  98       struct fiemap_extent *fm_extents = &fiemap->fm_extents[0];
  99       enum { count = (sizeof fiemap_buf - sizeof *fiemap)/sizeof *fm_extents };
 100       verify (count > 1);
 101
 102       /* This is required at least to initialize fiemap->fm_start,
 103          but also serves (in mid 2010) to appease valgrind, which
 104          appears not to know the semantics of the FIEMAP ioctl. */
 105       memset (&fiemap_buf, 0, sizeof fiemap_buf);
 106
 107       fiemap->fm_start = scan->scan_start;
 108       fiemap->fm_flags = scan->fm_flags;
 109       fiemap->fm_extent_count = count;
 110       fiemap->fm_length = FIEMAP_MAX_OFFSET - scan->scan_start;
 111
 112       /* Fall back to the standard copy if call ioctl(2) failed for
 113          the first time.  */
 114       if (ioctl (scan->fd, FS_IOC_FIEMAP, fiemap) < 0)
 115         {
 116           if (scan->scan_start == 0)
 117             scan->initial_scan_failed = true;
 118           return false;
 119         }
 120
 121       /* If 0 extents are returned, then no more scans are needed.  */
 122       if (fiemap->fm_mapped_extents == 0)
 123         {
 124           scan->hit_final_extent = true;
 125           return scan->scan_start != 0;
 126         }
 127
 128       assert (scan->ei_count <= SIZE_MAX - fiemap->fm_mapped_extents);
 129       scan->ei_count += fiemap->fm_mapped_extents;
 130       scan->ext_info = xnrealloc (scan->ext_info, scan->ei_count,
 131                                   sizeof (struct extent_info));
 132
 133       unsigned int i = 0;
 134       for (i = 0; i < fiemap->fm_mapped_extents; i++)
 135         {
 136           assert (fm_extents[i].fe_logical <=
 137                   OFF_T_MAX - fm_extents[i].fe_length);
 138
 139           if (si && last_ei->ext_flags ==
 140               (fm_extents[i].fe_flags & ~FIEMAP_EXTENT_LAST)
 141               && (last_ei->ext_logical + last_ei->ext_length
 142                   == fm_extents[i].fe_logical))
 143             {
 144               /* Merge previous with last.  */
 145               last_ei->ext_length += fm_extents[i].fe_length;
 146               /* Copy flags in case different.  */
 147               last_ei->ext_flags = fm_extents[i].fe_flags;
 148             }
 149           else if ((si == 0 && scan->scan_start > fm_extents[i].fe_logical)
 150                    || (si && last_ei->ext_logical + last_ei->ext_length >
 151                        fm_extents[i].fe_logical))
 152             {
 153               /* BTRFS before 2.6.38 could return overlapping extents
 154                  for sparse files.  We adjust the returned extents
 155                  rather than failing, as otherwise it would be inefficient
 156                  to detect this on the initial scan.  */
 157               uint64_t new_logical;
 158               uint64_t length_adjust;
 159               if (si == 0)
 160                 new_logical = scan->scan_start;
 161               else
 162                 {
 163                   /* We could return here if scan->scan_start == 0
 164                      but don't so as to minimize special cases.  */
 165                   new_logical = last_ei->ext_logical + last_ei->ext_length;
 166                 }
 167               length_adjust = new_logical - fm_extents[i].fe_logical;
 168               /* If an extent is contained within the previous one, fail.  */
 169               if (length_adjust < fm_extents[i].fe_length)
 170                 {
 171                   if (scan->scan_start == 0)
 172                     scan->initial_scan_failed = true;
 173                   return false;
 174                 }
 175               fm_extents[i].fe_logical = new_logical;
 176               fm_extents[i].fe_length -= length_adjust;
 177               /* Process the adjusted extent again.  */
 178               i--;
 179               continue;
 180             }
 181           else
 182             {
 183               last_ei = scan->ext_info + si;
 184               last_ei->ext_logical = fm_extents[i].fe_logical;
 185               last_ei->ext_length = fm_extents[i].fe_length;
 186               last_ei->ext_flags = fm_extents[i].fe_flags;
 187               si++;
 188             }
 189         }
 190
 191       if (last_ei->ext_flags & FIEMAP_EXTENT_LAST)
 192         scan->hit_final_extent = true;
 193
 194       /* If we have enough extents, discard the last as it might
 195          be merged with one from the next scan.  */
 196       if (si > count && !scan->hit_final_extent)
 197         last_ei = scan->ext_info + --si - 1;
 198
 199       /* We don't bother reallocating any trailing slots.  */
 200       scan->ei_count = si;
 201
 202       if (scan->hit_final_extent)
 203         break;
 204       else
 205         scan->scan_start = last_ei->ext_logical + last_ei->ext_length;
 206
 207       if (si >= count)
 208         break;
 209     }
 210
 211   return true;
 212 }
 213 #else
 214 extern bool
 215 extent_scan_read (struct extent_scan *scan ATTRIBUTE_UNUSED)
 216 {
 217   scan->initial_scan_failed = true;
 218   errno = ENOTSUP;
 219   return false;
 220 }
 221 #endif