The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/ntfs/compress.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /**
    2  * compress.c - NTFS kernel compressed attributes handling.
    3  *              Part of the Linux-NTFS project.
    4  *
    5  * Copyright (c) 2001-2004 Anton Altaparmakov
    6  * Copyright (c) 2002 Richard Russon
    7  *
    8  * This program/include file is free software; you can redistribute it and/or
    9  * modify it under the terms of the GNU General Public License as published
   10  * by the Free Software Foundation; either version 2 of the License, or
   11  * (at your option) any later version.
   12  *
   13  * This program/include file is distributed in the hope that it will be
   14  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
   15  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   16  * GNU General Public License for more details.
   17  *
   18  * You should have received a copy of the GNU General Public License
   19  * along with this program (in the main directory of the Linux-NTFS
   20  * distribution in the file COPYING); if not, write to the Free Software
   21  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   22  */
   23 
   24 #include <linux/fs.h>
   25 #include <linux/buffer_head.h>
   26 #include <linux/blkdev.h>
   27 #include <linux/vmalloc.h>
   28 #include <linux/slab.h>
   29 
   30 #include "attrib.h"
   31 #include "inode.h"
   32 #include "debug.h"
   33 #include "ntfs.h"
   34 
   35 /**
   36  * ntfs_compression_constants - enum of constants used in the compression code
   37  */
   38 typedef enum {
   39         /* Token types and access mask. */
   40         NTFS_SYMBOL_TOKEN       =       0,
   41         NTFS_PHRASE_TOKEN       =       1,
   42         NTFS_TOKEN_MASK         =       1,
   43 
   44         /* Compression sub-block constants. */
   45         NTFS_SB_SIZE_MASK       =       0x0fff,
   46         NTFS_SB_SIZE            =       0x1000,
   47         NTFS_SB_IS_COMPRESSED   =       0x8000,
   48 
   49         /*
   50          * The maximum compression block size is by definition 16 * the cluster
   51          * size, with the maximum supported cluster size being 4kiB. Thus the
   52          * maximum compression buffer size is 64kiB, so we use this when
   53          * initializing the compression buffer.
   54          */
   55         NTFS_MAX_CB_SIZE        = 64 * 1024,
   56 } ntfs_compression_constants;
   57 
   58 /**
   59  * ntfs_compression_buffer - one buffer for the decompression engine
   60  */
   61 static u8 *ntfs_compression_buffer = NULL;
   62 
   63 /**
   64  * ntfs_cb_lock - spinlock which protects ntfs_compression_buffer
   65  */
   66 static DEFINE_SPINLOCK(ntfs_cb_lock);
   67 
   68 /**
   69  * allocate_compression_buffers - allocate the decompression buffers
   70  *
   71  * Caller has to hold the ntfs_lock mutex.
   72  *
   73  * Return 0 on success or -ENOMEM if the allocations failed.
   74  */
   75 int allocate_compression_buffers(void)
   76 {
   77         BUG_ON(ntfs_compression_buffer);
   78 
   79         ntfs_compression_buffer = vmalloc(NTFS_MAX_CB_SIZE);
   80         if (!ntfs_compression_buffer)
   81                 return -ENOMEM;
   82         return 0;
   83 }
   84 
   85 /**
   86  * free_compression_buffers - free the decompression buffers
   87  *
   88  * Caller has to hold the ntfs_lock mutex.
   89  */
   90 void free_compression_buffers(void)
   91 {
   92         BUG_ON(!ntfs_compression_buffer);
   93         vfree(ntfs_compression_buffer);
   94         ntfs_compression_buffer = NULL;
   95 }
   96 
   97 /**
   98  * zero_partial_compressed_page - zero out of bounds compressed page region
   99  */
  100 static void zero_partial_compressed_page(struct page *page,
  101                 const s64 initialized_size)
  102 {
  103         u8 *kp = page_address(page);
  104         unsigned int kp_ofs;
  105 
  106         ntfs_debug("Zeroing page region outside initialized size.");
  107         if (((s64)page->index << PAGE_CACHE_SHIFT) >= initialized_size) {
  108                 /*
  109                  * FIXME: Using clear_page() will become wrong when we get
  110                  * PAGE_CACHE_SIZE != PAGE_SIZE but for now there is no problem.
  111                  */
  112                 clear_page(kp);
  113                 return;
  114         }
  115         kp_ofs = initialized_size & ~PAGE_CACHE_MASK;
  116         memset(kp + kp_ofs, 0, PAGE_CACHE_SIZE - kp_ofs);
  117         return;
  118 }
  119 
  120 /**
  121  * handle_bounds_compressed_page - test for&handle out of bounds compressed page
  122  */
  123 static inline void handle_bounds_compressed_page(struct page *page,
  124                 const loff_t i_size, const s64 initialized_size)
  125 {
  126         if ((page->index >= (initialized_size >> PAGE_CACHE_SHIFT)) &&
  127                         (initialized_size < i_size))
  128                 zero_partial_compressed_page(page, initialized_size);
  129         return;
  130 }
  131 
  132 /**
  133  * ntfs_decompress - decompress a compression block into an array of pages
  134  * @dest_pages:         destination array of pages
  135  * @dest_index:         current index into @dest_pages (IN/OUT)
  136  * @dest_ofs:           current offset within @dest_pages[@dest_index] (IN/OUT)
  137  * @dest_max_index:     maximum index into @dest_pages (IN)
  138  * @dest_max_ofs:       maximum offset within @dest_pages[@dest_max_index] (IN)
  139  * @xpage:              the target page (-1 if none) (IN)
  140  * @xpage_done:         set to 1 if xpage was completed successfully (IN/OUT)
  141  * @cb_start:           compression block to decompress (IN)
  142  * @cb_size:            size of compression block @cb_start in bytes (IN)
  143  * @i_size:             file size when we started the read (IN)
  144  * @initialized_size:   initialized file size when we started the read (IN)
  145  *
  146  * The caller must have disabled preemption. ntfs_decompress() reenables it when
  147  * the critical section is finished.
  148  *
  149  * This decompresses the compression block @cb_start into the array of
  150  * destination pages @dest_pages starting at index @dest_index into @dest_pages
  151  * and at offset @dest_pos into the page @dest_pages[@dest_index].
  152  *
  153  * When the page @dest_pages[@xpage] is completed, @xpage_done is set to 1.
  154  * If xpage is -1 or @xpage has not been completed, @xpage_done is not modified.
  155  *
  156  * @cb_start is a pointer to the compression block which needs decompressing
  157  * and @cb_size is the size of @cb_start in bytes (8-64kiB).
  158  *
  159  * Return 0 if success or -EOVERFLOW on error in the compressed stream.
  160  * @xpage_done indicates whether the target page (@dest_pages[@xpage]) was
  161  * completed during the decompression of the compression block (@cb_start).
  162  *
  163  * Warning: This function *REQUIRES* PAGE_CACHE_SIZE >= 4096 or it will blow up
  164  * unpredicatbly! You have been warned!
  165  *
  166  * Note to hackers: This function may not sleep until it has finished accessing
  167  * the compression block @cb_start as it is a per-CPU buffer.
  168  */
  169 static int ntfs_decompress(struct page *dest_pages[], int *dest_index,
  170                 int *dest_ofs, const int dest_max_index, const int dest_max_ofs,
  171                 const int xpage, char *xpage_done, u8 *const cb_start,
  172                 const u32 cb_size, const loff_t i_size,
  173                 const s64 initialized_size)
  174 {
  175         /*
  176          * Pointers into the compressed data, i.e. the compression block (cb),
  177          * and the therein contained sub-blocks (sb).
  178          */
  179         u8 *cb_end = cb_start + cb_size; /* End of cb. */
  180         u8 *cb = cb_start;      /* Current position in cb. */
  181         u8 *cb_sb_start = cb;   /* Beginning of the current sb in the cb. */
  182         u8 *cb_sb_end;          /* End of current sb / beginning of next sb. */
  183 
  184         /* Variables for uncompressed data / destination. */
  185         struct page *dp;        /* Current destination page being worked on. */
  186         u8 *dp_addr;            /* Current pointer into dp. */
  187         u8 *dp_sb_start;        /* Start of current sub-block in dp. */
  188         u8 *dp_sb_end;          /* End of current sb in dp (dp_sb_start +
  189                                    NTFS_SB_SIZE). */
  190         u16 do_sb_start;        /* @dest_ofs when starting this sub-block. */
  191         u16 do_sb_end;          /* @dest_ofs of end of this sb (do_sb_start +
  192                                    NTFS_SB_SIZE). */
  193 
  194         /* Variables for tag and token parsing. */
  195         u8 tag;                 /* Current tag. */
  196         int token;              /* Loop counter for the eight tokens in tag. */
  197 
  198         /* Need this because we can't sleep, so need two stages. */
  199         int completed_pages[dest_max_index - *dest_index + 1];
  200         int nr_completed_pages = 0;
  201 
  202         /* Default error code. */
  203         int err = -EOVERFLOW;
  204 
  205         ntfs_debug("Entering, cb_size = 0x%x.", cb_size);
  206 do_next_sb:
  207         ntfs_debug("Beginning sub-block at offset = 0x%zx in the cb.",
  208                         cb - cb_start);
  209         /*
  210          * Have we reached the end of the compression block or the end of the
  211          * decompressed data?  The latter can happen for example if the current
  212          * position in the compression block is one byte before its end so the
  213          * first two checks do not detect it.
  214          */
  215         if (cb == cb_end || !le16_to_cpup((le16*)cb) ||
  216                         (*dest_index == dest_max_index &&
  217                         *dest_ofs == dest_max_ofs)) {
  218                 int i;
  219 
  220                 ntfs_debug("Completed. Returning success (0).");
  221                 err = 0;
  222 return_error:
  223                 /* We can sleep from now on, so we drop lock. */
  224                 spin_unlock(&ntfs_cb_lock);
  225                 /* Second stage: finalize completed pages. */
  226                 if (nr_completed_pages > 0) {
  227                         for (i = 0; i < nr_completed_pages; i++) {
  228                                 int di = completed_pages[i];
  229 
  230                                 dp = dest_pages[di];
  231                                 /*
  232                                  * If we are outside the initialized size, zero
  233                                  * the out of bounds page range.
  234                                  */
  235                                 handle_bounds_compressed_page(dp, i_size,
  236                                                 initialized_size);
  237                                 flush_dcache_page(dp);
  238                                 kunmap(dp);
  239                                 SetPageUptodate(dp);
  240                                 unlock_page(dp);
  241                                 if (di == xpage)
  242                                         *xpage_done = 1;
  243                                 else
  244                                         page_cache_release(dp);
  245                                 dest_pages[di] = NULL;
  246                         }
  247                 }
  248                 return err;
  249         }
  250 
  251         /* Setup offsets for the current sub-block destination. */
  252         do_sb_start = *dest_ofs;
  253         do_sb_end = do_sb_start + NTFS_SB_SIZE;
  254 
  255         /* Check that we are still within allowed boundaries. */
  256         if (*dest_index == dest_max_index && do_sb_end > dest_max_ofs)
  257                 goto return_overflow;
  258 
  259         /* Does the minimum size of a compressed sb overflow valid range? */
  260         if (cb + 6 > cb_end)
  261                 goto return_overflow;
  262 
  263         /* Setup the current sub-block source pointers and validate range. */
  264         cb_sb_start = cb;
  265         cb_sb_end = cb_sb_start + (le16_to_cpup((le16*)cb) & NTFS_SB_SIZE_MASK)
  266                         + 3;
  267         if (cb_sb_end > cb_end)
  268                 goto return_overflow;
  269 
  270         /* Get the current destination page. */
  271         dp = dest_pages[*dest_index];
  272         if (!dp) {
  273                 /* No page present. Skip decompression of this sub-block. */
  274                 cb = cb_sb_end;
  275 
  276                 /* Advance destination position to next sub-block. */
  277                 *dest_ofs = (*dest_ofs + NTFS_SB_SIZE) & ~PAGE_CACHE_MASK;
  278                 if (!*dest_ofs && (++*dest_index > dest_max_index))
  279                         goto return_overflow;
  280                 goto do_next_sb;
  281         }
  282 
  283         /* We have a valid destination page. Setup the destination pointers. */
  284         dp_addr = (u8*)page_address(dp) + do_sb_start;
  285 
  286         /* Now, we are ready to process the current sub-block (sb). */
  287         if (!(le16_to_cpup((le16*)cb) & NTFS_SB_IS_COMPRESSED)) {
  288                 ntfs_debug("Found uncompressed sub-block.");
  289                 /* This sb is not compressed, just copy it into destination. */
  290 
  291                 /* Advance source position to first data byte. */
  292                 cb += 2;
  293 
  294                 /* An uncompressed sb must be full size. */
  295                 if (cb_sb_end - cb != NTFS_SB_SIZE)
  296                         goto return_overflow;
  297 
  298                 /* Copy the block and advance the source position. */
  299                 memcpy(dp_addr, cb, NTFS_SB_SIZE);
  300                 cb += NTFS_SB_SIZE;
  301 
  302                 /* Advance destination position to next sub-block. */
  303                 *dest_ofs += NTFS_SB_SIZE;
  304                 if (!(*dest_ofs &= ~PAGE_CACHE_MASK)) {
  305 finalize_page:
  306                         /*
  307                          * First stage: add current page index to array of
  308                          * completed pages.
  309                          */
  310                         completed_pages[nr_completed_pages++] = *dest_index;
  311                         if (++*dest_index > dest_max_index)
  312                                 goto return_overflow;
  313                 }
  314                 goto do_next_sb;
  315         }
  316         ntfs_debug("Found compressed sub-block.");
  317         /* This sb is compressed, decompress it into destination. */
  318 
  319         /* Setup destination pointers. */
  320         dp_sb_start = dp_addr;
  321         dp_sb_end = dp_sb_start + NTFS_SB_SIZE;
  322 
  323         /* Forward to the first tag in the sub-block. */
  324         cb += 2;
  325 do_next_tag:
  326         if (cb == cb_sb_end) {
  327                 /* Check if the decompressed sub-block was not full-length. */
  328                 if (dp_addr < dp_sb_end) {
  329                         int nr_bytes = do_sb_end - *dest_ofs;
  330 
  331                         ntfs_debug("Filling incomplete sub-block with "
  332                                         "zeroes.");
  333                         /* Zero remainder and update destination position. */
  334                         memset(dp_addr, 0, nr_bytes);
  335                         *dest_ofs += nr_bytes;
  336                 }
  337                 /* We have finished the current sub-block. */
  338                 if (!(*dest_ofs &= ~PAGE_CACHE_MASK))
  339                         goto finalize_page;
  340                 goto do_next_sb;
  341         }
  342 
  343         /* Check we are still in range. */
  344         if (cb > cb_sb_end || dp_addr > dp_sb_end)
  345                 goto return_overflow;
  346 
  347         /* Get the next tag and advance to first token. */
  348         tag = *cb++;
  349 
  350         /* Parse the eight tokens described by the tag. */
  351         for (token = 0; token < 8; token++, tag >>= 1) {
  352                 u16 lg, pt, length, max_non_overlap;
  353                 register u16 i;
  354                 u8 *dp_back_addr;
  355 
  356                 /* Check if we are done / still in range. */
  357                 if (cb >= cb_sb_end || dp_addr > dp_sb_end)
  358                         break;
  359 
  360                 /* Determine token type and parse appropriately.*/
  361                 if ((tag & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) {
  362                         /*
  363                          * We have a symbol token, copy the symbol across, and
  364                          * advance the source and destination positions.
  365                          */
  366                         *dp_addr++ = *cb++;
  367                         ++*dest_ofs;
  368 
  369                         /* Continue with the next token. */
  370                         continue;
  371                 }
  372 
  373                 /*
  374                  * We have a phrase token. Make sure it is not the first tag in
  375                  * the sb as this is illegal and would confuse the code below.
  376                  */
  377                 if (dp_addr == dp_sb_start)
  378                         goto return_overflow;
  379 
  380                 /*
  381                  * Determine the number of bytes to go back (p) and the number
  382                  * of bytes to copy (l). We use an optimized algorithm in which
  383                  * we first calculate log2(current destination position in sb),
  384                  * which allows determination of l and p in O(1) rather than
  385                  * O(n). We just need an arch-optimized log2() function now.
  386                  */
  387                 lg = 0;
  388                 for (i = *dest_ofs - do_sb_start - 1; i >= 0x10; i >>= 1)
  389                         lg++;
  390 
  391                 /* Get the phrase token into i. */
  392                 pt = le16_to_cpup((le16*)cb);
  393 
  394                 /*
  395                  * Calculate starting position of the byte sequence in
  396                  * the destination using the fact that p = (pt >> (12 - lg)) + 1
  397                  * and make sure we don't go too far back.
  398                  */
  399                 dp_back_addr = dp_addr - (pt >> (12 - lg)) - 1;
  400                 if (dp_back_addr < dp_sb_start)
  401                         goto return_overflow;
  402 
  403                 /* Now calculate the length of the byte sequence. */
  404                 length = (pt & (0xfff >> lg)) + 3;
  405 
  406                 /* Advance destination position and verify it is in range. */
  407                 *dest_ofs += length;
  408                 if (*dest_ofs > do_sb_end)
  409                         goto return_overflow;
  410 
  411                 /* The number of non-overlapping bytes. */
  412                 max_non_overlap = dp_addr - dp_back_addr;
  413 
  414                 if (length <= max_non_overlap) {
  415                         /* The byte sequence doesn't overlap, just copy it. */
  416                         memcpy(dp_addr, dp_back_addr, length);
  417 
  418                         /* Advance destination pointer. */
  419                         dp_addr += length;
  420                 } else {
  421                         /*
  422                          * The byte sequence does overlap, copy non-overlapping
  423                          * part and then do a slow byte by byte copy for the
  424                          * overlapping part. Also, advance the destination
  425                          * pointer.
  426                          */
  427                         memcpy(dp_addr, dp_back_addr, max_non_overlap);
  428                         dp_addr += max_non_overlap;
  429                         dp_back_addr += max_non_overlap;
  430                         length -= max_non_overlap;
  431                         while (length--)
  432                                 *dp_addr++ = *dp_back_addr++;
  433                 }
  434 
  435                 /* Advance source position and continue with the next token. */
  436                 cb += 2;
  437         }
  438 
  439         /* No tokens left in the current tag. Continue with the next tag. */
  440         goto do_next_tag;
  441 
  442 return_overflow:
  443         ntfs_error(NULL, "Failed. Returning -EOVERFLOW.");
  444         goto return_error;
  445 }
  446 
  447 /**
  448  * ntfs_read_compressed_block - read a compressed block into the page cache
  449  * @page:       locked page in the compression block(s) we need to read
  450  *
  451  * When we are called the page has already been verified to be locked and the
  452  * attribute is known to be non-resident, not encrypted, but compressed.
  453  *
  454  * 1. Determine which compression block(s) @page is in.
  455  * 2. Get hold of all pages corresponding to this/these compression block(s).
  456  * 3. Read the (first) compression block.
  457  * 4. Decompress it into the corresponding pages.
  458  * 5. Throw the compressed data away and proceed to 3. for the next compression
  459  *    block or return success if no more compression blocks left.
  460  *
  461  * Warning: We have to be careful what we do about existing pages. They might
  462  * have been written to so that we would lose data if we were to just overwrite
  463  * them with the out-of-date uncompressed data.
  464  *
  465  * FIXME: For PAGE_CACHE_SIZE > cb_size we are not doing the Right Thing(TM) at
  466  * the end of the file I think. We need to detect this case and zero the out
  467  * of bounds remainder of the page in question and mark it as handled. At the
  468  * moment we would just return -EIO on such a page. This bug will only become
  469  * apparent if pages are above 8kiB and the NTFS volume only uses 512 byte
  470  * clusters so is probably not going to be seen by anyone. Still this should
  471  * be fixed. (AIA)
  472  *
  473  * FIXME: Again for PAGE_CACHE_SIZE > cb_size we are screwing up both in
  474  * handling sparse and compressed cbs. (AIA)
  475  *
  476  * FIXME: At the moment we don't do any zeroing out in the case that
  477  * initialized_size is less than data_size. This should be safe because of the
  478  * nature of the compression algorithm used. Just in case we check and output
  479  * an error message in read inode if the two sizes are not equal for a
  480  * compressed file. (AIA)
  481  */
  482 int ntfs_read_compressed_block(struct page *page)
  483 {
  484         loff_t i_size;
  485         s64 initialized_size;
  486         struct address_space *mapping = page->mapping;
  487         ntfs_inode *ni = NTFS_I(mapping->host);
  488         ntfs_volume *vol = ni->vol;
  489         struct super_block *sb = vol->sb;
  490         runlist_element *rl;
  491         unsigned long flags, block_size = sb->s_blocksize;
  492         unsigned char block_size_bits = sb->s_blocksize_bits;
  493         u8 *cb, *cb_pos, *cb_end;
  494         struct buffer_head **bhs;
  495         unsigned long offset, index = page->index;
  496         u32 cb_size = ni->itype.compressed.block_size;
  497         u64 cb_size_mask = cb_size - 1UL;
  498         VCN vcn;
  499         LCN lcn;
  500         /* The first wanted vcn (minimum alignment is PAGE_CACHE_SIZE). */
  501         VCN start_vcn = (((s64)index << PAGE_CACHE_SHIFT) & ~cb_size_mask) >>
  502                         vol->cluster_size_bits;
  503         /*
  504          * The first vcn after the last wanted vcn (minimum alignment is again
  505          * PAGE_CACHE_SIZE.
  506          */
  507         VCN end_vcn = ((((s64)(index + 1UL) << PAGE_CACHE_SHIFT) + cb_size - 1)
  508                         & ~cb_size_mask) >> vol->cluster_size_bits;
  509         /* Number of compression blocks (cbs) in the wanted vcn range. */
  510         unsigned int nr_cbs = (end_vcn - start_vcn) << vol->cluster_size_bits
  511                         >> ni->itype.compressed.block_size_bits;
  512         /*
  513          * Number of pages required to store the uncompressed data from all
  514          * compression blocks (cbs) overlapping @page. Due to alignment
  515          * guarantees of start_vcn and end_vcn, no need to round up here.
  516          */
  517         unsigned int nr_pages = (end_vcn - start_vcn) <<
  518                         vol->cluster_size_bits >> PAGE_CACHE_SHIFT;
  519         unsigned int xpage, max_page, cur_page, cur_ofs, i;
  520         unsigned int cb_clusters, cb_max_ofs;
  521         int block, max_block, cb_max_page, bhs_size, nr_bhs, err = 0;
  522         struct page **pages;
  523         unsigned char xpage_done = 0;
  524 
  525         ntfs_debug("Entering, page->index = 0x%lx, cb_size = 0x%x, nr_pages = "
  526                         "%i.", index, cb_size, nr_pages);
  527         /*
  528          * Bad things happen if we get here for anything that is not an
  529          * unnamed $DATA attribute.
  530          */
  531         BUG_ON(ni->type != AT_DATA);
  532         BUG_ON(ni->name_len);
  533 
  534         pages = kmalloc(nr_pages * sizeof(struct page *), GFP_NOFS);
  535 
  536         /* Allocate memory to store the buffer heads we need. */
  537         bhs_size = cb_size / block_size * sizeof(struct buffer_head *);
  538         bhs = kmalloc(bhs_size, GFP_NOFS);
  539 
  540         if (unlikely(!pages || !bhs)) {
  541                 kfree(bhs);
  542                 kfree(pages);
  543                 unlock_page(page);
  544                 ntfs_error(vol->sb, "Failed to allocate internal buffers.");
  545                 return -ENOMEM;
  546         }
  547 
  548         /*
  549          * We have already been given one page, this is the one we must do.
  550          * Once again, the alignment guarantees keep it simple.
  551          */
  552         offset = start_vcn << vol->cluster_size_bits >> PAGE_CACHE_SHIFT;
  553         xpage = index - offset;
  554         pages[xpage] = page;
  555         /*
  556          * The remaining pages need to be allocated and inserted into the page
  557          * cache, alignment guarantees keep all the below much simpler. (-8
  558          */
  559         read_lock_irqsave(&ni->size_lock, flags);
  560         i_size = i_size_read(VFS_I(ni));
  561         initialized_size = ni->initialized_size;
  562         read_unlock_irqrestore(&ni->size_lock, flags);
  563         max_page = ((i_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT) -
  564                         offset;
  565         /* Is the page fully outside i_size? (truncate in progress) */
  566         if (xpage >= max_page) {
  567                 kfree(bhs);
  568                 kfree(pages);
  569                 zero_user(page, 0, PAGE_CACHE_SIZE);
  570                 ntfs_debug("Compressed read outside i_size - truncated?");
  571                 SetPageUptodate(page);
  572                 unlock_page(page);
  573                 return 0;
  574         }
  575         if (nr_pages < max_page)
  576                 max_page = nr_pages;
  577         for (i = 0; i < max_page; i++, offset++) {
  578                 if (i != xpage)
  579                         pages[i] = grab_cache_page_nowait(mapping, offset);
  580                 page = pages[i];
  581                 if (page) {
  582                         /*
  583                          * We only (re)read the page if it isn't already read
  584                          * in and/or dirty or we would be losing data or at
  585                          * least wasting our time.
  586                          */
  587                         if (!PageDirty(page) && (!PageUptodate(page) ||
  588                                         PageError(page))) {
  589                                 ClearPageError(page);
  590                                 kmap(page);
  591                                 continue;
  592                         }
  593                         unlock_page(page);
  594                         page_cache_release(page);
  595                         pages[i] = NULL;
  596                 }
  597         }
  598 
  599         /*
  600          * We have the runlist, and all the destination pages we need to fill.
  601          * Now read the first compression block.
  602          */
  603         cur_page = 0;
  604         cur_ofs = 0;
  605         cb_clusters = ni->itype.compressed.block_clusters;
  606 do_next_cb:
  607         nr_cbs--;
  608         nr_bhs = 0;
  609 
  610         /* Read all cb buffer heads one cluster at a time. */
  611         rl = NULL;
  612         for (vcn = start_vcn, start_vcn += cb_clusters; vcn < start_vcn;
  613                         vcn++) {
  614                 bool is_retry = false;
  615 
  616                 if (!rl) {
  617 lock_retry_remap:
  618                         down_read(&ni->runlist.lock);
  619                         rl = ni->runlist.rl;
  620                 }
  621                 if (likely(rl != NULL)) {
  622                         /* Seek to element containing target vcn. */
  623                         while (rl->length && rl[1].vcn <= vcn)
  624                                 rl++;
  625                         lcn = ntfs_rl_vcn_to_lcn(rl, vcn);
  626                 } else
  627                         lcn = LCN_RL_NOT_MAPPED;
  628                 ntfs_debug("Reading vcn = 0x%llx, lcn = 0x%llx.",
  629                                 (unsigned long long)vcn,
  630                                 (unsigned long long)lcn);
  631                 if (lcn < 0) {
  632                         /*
  633                          * When we reach the first sparse cluster we have
  634                          * finished with the cb.
  635                          */
  636                         if (lcn == LCN_HOLE)
  637                                 break;
  638                         if (is_retry || lcn != LCN_RL_NOT_MAPPED)
  639                                 goto rl_err;
  640                         is_retry = true;
  641                         /*
  642                          * Attempt to map runlist, dropping lock for the
  643                          * duration.
  644                          */
  645                         up_read(&ni->runlist.lock);
  646                         if (!ntfs_map_runlist(ni, vcn))
  647                                 goto lock_retry_remap;
  648                         goto map_rl_err;
  649                 }
  650                 block = lcn << vol->cluster_size_bits >> block_size_bits;
  651                 /* Read the lcn from device in chunks of block_size bytes. */
  652                 max_block = block + (vol->cluster_size >> block_size_bits);
  653                 do {
  654                         ntfs_debug("block = 0x%x.", block);
  655                         if (unlikely(!(bhs[nr_bhs] = sb_getblk(sb, block))))
  656                                 goto getblk_err;
  657                         nr_bhs++;
  658                 } while (++block < max_block);
  659         }
  660 
  661         /* Release the lock if we took it. */
  662         if (rl)
  663                 up_read(&ni->runlist.lock);
  664 
  665         /* Setup and initiate io on all buffer heads. */
  666         for (i = 0; i < nr_bhs; i++) {
  667                 struct buffer_head *tbh = bhs[i];
  668 
  669                 if (!trylock_buffer(tbh))
  670                         continue;
  671                 if (unlikely(buffer_uptodate(tbh))) {
  672                         unlock_buffer(tbh);
  673                         continue;
  674                 }
  675                 get_bh(tbh);
  676                 tbh->b_end_io = end_buffer_read_sync;
  677                 submit_bh(READ, tbh);
  678         }
  679 
  680         /* Wait for io completion on all buffer heads. */
  681         for (i = 0; i < nr_bhs; i++) {
  682                 struct buffer_head *tbh = bhs[i];
  683 
  684                 if (buffer_uptodate(tbh))
  685                         continue;
  686                 wait_on_buffer(tbh);
  687                 /*
  688                  * We need an optimization barrier here, otherwise we start
  689                  * hitting the below fixup code when accessing a loopback
  690                  * mounted ntfs partition. This indicates either there is a
  691                  * race condition in the loop driver or, more likely, gcc
  692                  * overoptimises the code without the barrier and it doesn't
  693                  * do the Right Thing(TM).
  694                  */
  695                 barrier();
  696                 if (unlikely(!buffer_uptodate(tbh))) {
  697                         ntfs_warning(vol->sb, "Buffer is unlocked but not "
  698                                         "uptodate! Unplugging the disk queue "
  699                                         "and rescheduling.");
  700                         get_bh(tbh);
  701                         io_schedule();
  702                         put_bh(tbh);
  703                         if (unlikely(!buffer_uptodate(tbh)))
  704                                 goto read_err;
  705                         ntfs_warning(vol->sb, "Buffer is now uptodate. Good.");
  706                 }
  707         }
  708 
  709         /*
  710          * Get the compression buffer. We must not sleep any more
  711          * until we are finished with it.
  712          */
  713         spin_lock(&ntfs_cb_lock);
  714         cb = ntfs_compression_buffer;
  715 
  716         BUG_ON(!cb);
  717 
  718         cb_pos = cb;
  719         cb_end = cb + cb_size;
  720 
  721         /* Copy the buffer heads into the contiguous buffer. */
  722         for (i = 0; i < nr_bhs; i++) {
  723                 memcpy(cb_pos, bhs[i]->b_data, block_size);
  724                 cb_pos += block_size;
  725         }
  726 
  727         /* Just a precaution. */
  728         if (cb_pos + 2 <= cb + cb_size)
  729                 *(u16*)cb_pos = 0;
  730 
  731         /* Reset cb_pos back to the beginning. */
  732         cb_pos = cb;
  733 
  734         /* We now have both source (if present) and destination. */
  735         ntfs_debug("Successfully read the compression block.");
  736 
  737         /* The last page and maximum offset within it for the current cb. */
  738         cb_max_page = (cur_page << PAGE_CACHE_SHIFT) + cur_ofs + cb_size;
  739         cb_max_ofs = cb_max_page & ~PAGE_CACHE_MASK;
  740         cb_max_page >>= PAGE_CACHE_SHIFT;
  741 
  742         /* Catch end of file inside a compression block. */
  743         if (cb_max_page > max_page)
  744                 cb_max_page = max_page;
  745 
  746         if (vcn == start_vcn - cb_clusters) {
  747                 /* Sparse cb, zero out page range overlapping the cb. */
  748                 ntfs_debug("Found sparse compression block.");
  749                 /* We can sleep from now on, so we drop lock. */
  750                 spin_unlock(&ntfs_cb_lock);
  751                 if (cb_max_ofs)
  752                         cb_max_page--;
  753                 for (; cur_page < cb_max_page; cur_page++) {
  754                         page = pages[cur_page];
  755                         if (page) {
  756                                 /*
  757                                  * FIXME: Using clear_page() will become wrong
  758                                  * when we get PAGE_CACHE_SIZE != PAGE_SIZE but
  759                                  * for now there is no problem.
  760                                  */
  761                                 if (likely(!cur_ofs))
  762                                         clear_page(page_address(page));
  763                                 else
  764                                         memset(page_address(page) + cur_ofs, 0,
  765                                                         PAGE_CACHE_SIZE -
  766                                                         cur_ofs);
  767                                 flush_dcache_page(page);
  768                                 kunmap(page);
  769                                 SetPageUptodate(page);
  770                                 unlock_page(page);
  771                                 if (cur_page == xpage)
  772                                         xpage_done = 1;
  773                                 else
  774                                         page_cache_release(page);
  775                                 pages[cur_page] = NULL;
  776                         }
  777                         cb_pos += PAGE_CACHE_SIZE - cur_ofs;
  778                         cur_ofs = 0;
  779                         if (cb_pos >= cb_end)
  780                                 break;
  781                 }
  782                 /* If we have a partial final page, deal with it now. */
  783                 if (cb_max_ofs && cb_pos < cb_end) {
  784                         page = pages[cur_page];
  785                         if (page)
  786                                 memset(page_address(page) + cur_ofs, 0,
  787                                                 cb_max_ofs - cur_ofs);
  788                         /*
  789                          * No need to update cb_pos at this stage:
  790                          *      cb_pos += cb_max_ofs - cur_ofs;
  791                          */
  792                         cur_ofs = cb_max_ofs;
  793                 }
  794         } else if (vcn == start_vcn) {
  795                 /* We can't sleep so we need two stages. */
  796                 unsigned int cur2_page = cur_page;
  797                 unsigned int cur_ofs2 = cur_ofs;
  798                 u8 *cb_pos2 = cb_pos;
  799 
  800                 ntfs_debug("Found uncompressed compression block.");
  801                 /* Uncompressed cb, copy it to the destination pages. */
  802                 /*
  803                  * TODO: As a big optimization, we could detect this case
  804                  * before we read all the pages and use block_read_full_page()
  805                  * on all full pages instead (we still have to treat partial
  806                  * pages especially but at least we are getting rid of the
  807                  * synchronous io for the majority of pages.
  808                  * Or if we choose not to do the read-ahead/-behind stuff, we
  809                  * could just return block_read_full_page(pages[xpage]) as long
  810                  * as PAGE_CACHE_SIZE <= cb_size.
  811                  */
  812                 if (cb_max_ofs)
  813                         cb_max_page--;
  814                 /* First stage: copy data into destination pages. */
  815                 for (; cur_page < cb_max_page; cur_page++) {
  816                         page = pages[cur_page];
  817                         if (page)
  818                                 memcpy(page_address(page) + cur_ofs, cb_pos,
  819                                                 PAGE_CACHE_SIZE - cur_ofs);
  820                         cb_pos += PAGE_CACHE_SIZE - cur_ofs;
  821                         cur_ofs = 0;
  822                         if (cb_pos >= cb_end)
  823                                 break;
  824                 }
  825                 /* If we have a partial final page, deal with it now. */
  826                 if (cb_max_ofs && cb_pos < cb_end) {
  827                         page = pages[cur_page];
  828                         if (page)
  829                                 memcpy(page_address(page) + cur_ofs, cb_pos,
  830                                                 cb_max_ofs - cur_ofs);
  831                         cb_pos += cb_max_ofs - cur_ofs;
  832                         cur_ofs = cb_max_ofs;
  833                 }
  834                 /* We can sleep from now on, so drop lock. */
  835                 spin_unlock(&ntfs_cb_lock);
  836                 /* Second stage: finalize pages. */
  837                 for (; cur2_page < cb_max_page; cur2_page++) {
  838                         page = pages[cur2_page];
  839                         if (page) {
  840                                 /*
  841                                  * If we are outside the initialized size, zero
  842                                  * the out of bounds page range.
  843                                  */
  844                                 handle_bounds_compressed_page(page, i_size,
  845                                                 initialized_size);
  846                                 flush_dcache_page(page);
  847                                 kunmap(page);
  848                                 SetPageUptodate(page);
  849                                 unlock_page(page);
  850                                 if (cur2_page == xpage)
  851                                         xpage_done = 1;
  852                                 else
  853                                         page_cache_release(page);
  854                                 pages[cur2_page] = NULL;
  855                         }
  856                         cb_pos2 += PAGE_CACHE_SIZE - cur_ofs2;
  857                         cur_ofs2 = 0;
  858                         if (cb_pos2 >= cb_end)
  859                                 break;
  860                 }
  861         } else {
  862                 /* Compressed cb, decompress it into the destination page(s). */
  863                 unsigned int prev_cur_page = cur_page;
  864 
  865                 ntfs_debug("Found compressed compression block.");
  866                 err = ntfs_decompress(pages, &cur_page, &cur_ofs,
  867                                 cb_max_page, cb_max_ofs, xpage, &xpage_done,
  868                                 cb_pos, cb_size - (cb_pos - cb), i_size,
  869                                 initialized_size);
  870                 /*
  871                  * We can sleep from now on, lock already dropped by
  872                  * ntfs_decompress().
  873                  */
  874                 if (err) {
  875                         ntfs_error(vol->sb, "ntfs_decompress() failed in inode "
  876                                         "0x%lx with error code %i. Skipping "
  877                                         "this compression block.",
  878                                         ni->mft_no, -err);
  879                         /* Release the unfinished pages. */
  880                         for (; prev_cur_page < cur_page; prev_cur_page++) {
  881                                 page = pages[prev_cur_page];
  882                                 if (page) {
  883                                         flush_dcache_page(page);
  884                                         kunmap(page);
  885                                         unlock_page(page);
  886                                         if (prev_cur_page != xpage)
  887                                                 page_cache_release(page);
  888                                         pages[prev_cur_page] = NULL;
  889                                 }
  890                         }
  891                 }
  892         }
  893 
  894         /* Release the buffer heads. */
  895         for (i = 0; i < nr_bhs; i++)
  896                 brelse(bhs[i]);
  897 
  898         /* Do we have more work to do? */
  899         if (nr_cbs)
  900                 goto do_next_cb;
  901 
  902         /* We no longer need the list of buffer heads. */
  903         kfree(bhs);
  904 
  905         /* Clean up if we have any pages left. Should never happen. */
  906         for (cur_page = 0; cur_page < max_page; cur_page++) {
  907                 page = pages[cur_page];
  908                 if (page) {
  909                         ntfs_error(vol->sb, "Still have pages left! "
  910                                         "Terminating them with extreme "
  911                                         "prejudice.  Inode 0x%lx, page index "
  912                                         "0x%lx.", ni->mft_no, page->index);
  913                         flush_dcache_page(page);
  914                         kunmap(page);
  915                         unlock_page(page);
  916                         if (cur_page != xpage)
  917                                 page_cache_release(page);
  918                         pages[cur_page] = NULL;
  919                 }
  920         }
  921 
  922         /* We no longer need the list of pages. */
  923         kfree(pages);
  924 
  925         /* If we have completed the requested page, we return success. */
  926         if (likely(xpage_done))
  927                 return 0;
  928 
  929         ntfs_debug("Failed. Returning error code %s.", err == -EOVERFLOW ?
  930                         "EOVERFLOW" : (!err ? "EIO" : "unknown error"));
  931         return err < 0 ? err : -EIO;
  932 
  933 read_err:
  934         ntfs_error(vol->sb, "IO error while reading compressed data.");
  935         /* Release the buffer heads. */
  936         for (i = 0; i < nr_bhs; i++)
  937                 brelse(bhs[i]);
  938         goto err_out;
  939 
  940 map_rl_err:
  941         ntfs_error(vol->sb, "ntfs_map_runlist() failed. Cannot read "
  942                         "compression block.");
  943         goto err_out;
  944 
  945 rl_err:
  946         up_read(&ni->runlist.lock);
  947         ntfs_error(vol->sb, "ntfs_rl_vcn_to_lcn() failed. Cannot read "
  948                         "compression block.");
  949         goto err_out;
  950 
  951 getblk_err:
  952         up_read(&ni->runlist.lock);
  953         ntfs_error(vol->sb, "getblk() failed. Cannot read compression block.");
  954 
  955 err_out:
  956         kfree(bhs);
  957         for (i = cur_page; i < max_page; i++) {
  958                 page = pages[i];
  959                 if (page) {
  960                         flush_dcache_page(page);
  961                         kunmap(page);
  962                         unlock_page(page);
  963                         if (i != xpage)
  964                                 page_cache_release(page);
  965                 }
  966         }
  967         kfree(pages);
  968         return -EIO;
  969 }

Cache object: b069c78bd20d7e124a61860cd5fb5e11


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.