1a1d312deSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later
2aa0b42b7SRandy Dunlap /*
31da177e4SLinus Torvalds * compress.c - NTFS kernel compressed attributes handling.
41da177e4SLinus Torvalds * Part of the Linux-NTFS project.
51da177e4SLinus Torvalds *
61da177e4SLinus Torvalds * Copyright (c) 2001-2004 Anton Altaparmakov
71da177e4SLinus Torvalds * Copyright (c) 2002 Richard Russon
81da177e4SLinus Torvalds */
91da177e4SLinus Torvalds
101da177e4SLinus Torvalds #include <linux/fs.h>
111da177e4SLinus Torvalds #include <linux/buffer_head.h>
121da177e4SLinus Torvalds #include <linux/blkdev.h>
131da177e4SLinus Torvalds #include <linux/vmalloc.h>
145a0e3ad6STejun Heo #include <linux/slab.h>
151da177e4SLinus Torvalds
161da177e4SLinus Torvalds #include "attrib.h"
171da177e4SLinus Torvalds #include "inode.h"
181da177e4SLinus Torvalds #include "debug.h"
191da177e4SLinus Torvalds #include "ntfs.h"
201da177e4SLinus Torvalds
211da177e4SLinus Torvalds /**
221da177e4SLinus Torvalds * ntfs_compression_constants - enum of constants used in the compression code
231da177e4SLinus Torvalds */
241da177e4SLinus Torvalds typedef enum {
251da177e4SLinus Torvalds /* Token types and access mask. */
261da177e4SLinus Torvalds NTFS_SYMBOL_TOKEN = 0,
271da177e4SLinus Torvalds NTFS_PHRASE_TOKEN = 1,
281da177e4SLinus Torvalds NTFS_TOKEN_MASK = 1,
291da177e4SLinus Torvalds
301da177e4SLinus Torvalds /* Compression sub-block constants. */
311da177e4SLinus Torvalds NTFS_SB_SIZE_MASK = 0x0fff,
321da177e4SLinus Torvalds NTFS_SB_SIZE = 0x1000,
331da177e4SLinus Torvalds NTFS_SB_IS_COMPRESSED = 0x8000,
341da177e4SLinus Torvalds
351da177e4SLinus Torvalds /*
361da177e4SLinus Torvalds * The maximum compression block size is by definition 16 * the cluster
371da177e4SLinus Torvalds * size, with the maximum supported cluster size being 4kiB. Thus the
381da177e4SLinus Torvalds * maximum compression buffer size is 64kiB, so we use this when
391da177e4SLinus Torvalds * initializing the compression buffer.
401da177e4SLinus Torvalds */
411da177e4SLinus Torvalds NTFS_MAX_CB_SIZE = 64 * 1024,
421da177e4SLinus Torvalds } ntfs_compression_constants;
431da177e4SLinus Torvalds
44aa0b42b7SRandy Dunlap /*
451da177e4SLinus Torvalds * ntfs_compression_buffer - one buffer for the decompression engine
461da177e4SLinus Torvalds */
47504e0e2fSFabian Frederick static u8 *ntfs_compression_buffer;
481da177e4SLinus Torvalds
49aa0b42b7SRandy Dunlap /*
501da177e4SLinus Torvalds * ntfs_cb_lock - spinlock which protects ntfs_compression_buffer
511da177e4SLinus Torvalds */
521da177e4SLinus Torvalds static DEFINE_SPINLOCK(ntfs_cb_lock);
531da177e4SLinus Torvalds
541da177e4SLinus Torvalds /**
551da177e4SLinus Torvalds * allocate_compression_buffers - allocate the decompression buffers
561da177e4SLinus Torvalds *
574e5e529aSIngo Molnar * Caller has to hold the ntfs_lock mutex.
581da177e4SLinus Torvalds *
591da177e4SLinus Torvalds * Return 0 on success or -ENOMEM if the allocations failed.
601da177e4SLinus Torvalds */
allocate_compression_buffers(void)611da177e4SLinus Torvalds int allocate_compression_buffers(void)
621da177e4SLinus Torvalds {
631da177e4SLinus Torvalds BUG_ON(ntfs_compression_buffer);
641da177e4SLinus Torvalds
651da177e4SLinus Torvalds ntfs_compression_buffer = vmalloc(NTFS_MAX_CB_SIZE);
661da177e4SLinus Torvalds if (!ntfs_compression_buffer)
671da177e4SLinus Torvalds return -ENOMEM;
681da177e4SLinus Torvalds return 0;
691da177e4SLinus Torvalds }
701da177e4SLinus Torvalds
711da177e4SLinus Torvalds /**
721da177e4SLinus Torvalds * free_compression_buffers - free the decompression buffers
731da177e4SLinus Torvalds *
744e5e529aSIngo Molnar * Caller has to hold the ntfs_lock mutex.
751da177e4SLinus Torvalds */
free_compression_buffers(void)761da177e4SLinus Torvalds void free_compression_buffers(void)
771da177e4SLinus Torvalds {
781da177e4SLinus Torvalds BUG_ON(!ntfs_compression_buffer);
791da177e4SLinus Torvalds vfree(ntfs_compression_buffer);
801da177e4SLinus Torvalds ntfs_compression_buffer = NULL;
811da177e4SLinus Torvalds }
821da177e4SLinus Torvalds
831da177e4SLinus Torvalds /**
841da177e4SLinus Torvalds * zero_partial_compressed_page - zero out of bounds compressed page region
851da177e4SLinus Torvalds */
zero_partial_compressed_page(struct page * page,const s64 initialized_size)8636763677SAnton Altaparmakov static void zero_partial_compressed_page(struct page *page,
8736763677SAnton Altaparmakov const s64 initialized_size)
881da177e4SLinus Torvalds {
891da177e4SLinus Torvalds u8 *kp = page_address(page);
901da177e4SLinus Torvalds unsigned int kp_ofs;
911da177e4SLinus Torvalds
921da177e4SLinus Torvalds ntfs_debug("Zeroing page region outside initialized size.");
9309cbfeafSKirill A. Shutemov if (((s64)page->index << PAGE_SHIFT) >= initialized_size) {
941da177e4SLinus Torvalds clear_page(kp);
951da177e4SLinus Torvalds return;
961da177e4SLinus Torvalds }
9709cbfeafSKirill A. Shutemov kp_ofs = initialized_size & ~PAGE_MASK;
9809cbfeafSKirill A. Shutemov memset(kp + kp_ofs, 0, PAGE_SIZE - kp_ofs);
991da177e4SLinus Torvalds return;
1001da177e4SLinus Torvalds }
1011da177e4SLinus Torvalds
1021da177e4SLinus Torvalds /**
1031da177e4SLinus Torvalds * handle_bounds_compressed_page - test for&handle out of bounds compressed page
1041da177e4SLinus Torvalds */
handle_bounds_compressed_page(struct page * page,const loff_t i_size,const s64 initialized_size)10536763677SAnton Altaparmakov static inline void handle_bounds_compressed_page(struct page *page,
10636763677SAnton Altaparmakov const loff_t i_size, const s64 initialized_size)
1071da177e4SLinus Torvalds {
10809cbfeafSKirill A. Shutemov if ((page->index >= (initialized_size >> PAGE_SHIFT)) &&
10936763677SAnton Altaparmakov (initialized_size < i_size))
11036763677SAnton Altaparmakov zero_partial_compressed_page(page, initialized_size);
1111da177e4SLinus Torvalds return;
1121da177e4SLinus Torvalds }
1131da177e4SLinus Torvalds
1141da177e4SLinus Torvalds /**
1151da177e4SLinus Torvalds * ntfs_decompress - decompress a compression block into an array of pages
1161da177e4SLinus Torvalds * @dest_pages: destination array of pages
1172c27ce91SKees Cook * @completed_pages: scratch space to track completed pages
1181da177e4SLinus Torvalds * @dest_index: current index into @dest_pages (IN/OUT)
1191da177e4SLinus Torvalds * @dest_ofs: current offset within @dest_pages[@dest_index] (IN/OUT)
1201da177e4SLinus Torvalds * @dest_max_index: maximum index into @dest_pages (IN)
1211da177e4SLinus Torvalds * @dest_max_ofs: maximum offset within @dest_pages[@dest_max_index] (IN)
1221da177e4SLinus Torvalds * @xpage: the target page (-1 if none) (IN)
1231da177e4SLinus Torvalds * @xpage_done: set to 1 if xpage was completed successfully (IN/OUT)
1241da177e4SLinus Torvalds * @cb_start: compression block to decompress (IN)
1251da177e4SLinus Torvalds * @cb_size: size of compression block @cb_start in bytes (IN)
12636763677SAnton Altaparmakov * @i_size: file size when we started the read (IN)
12736763677SAnton Altaparmakov * @initialized_size: initialized file size when we started the read (IN)
1281da177e4SLinus Torvalds *
1291da177e4SLinus Torvalds * The caller must have disabled preemption. ntfs_decompress() reenables it when
1301da177e4SLinus Torvalds * the critical section is finished.
1311da177e4SLinus Torvalds *
1321da177e4SLinus Torvalds * This decompresses the compression block @cb_start into the array of
1331da177e4SLinus Torvalds * destination pages @dest_pages starting at index @dest_index into @dest_pages
1341da177e4SLinus Torvalds * and at offset @dest_pos into the page @dest_pages[@dest_index].
1351da177e4SLinus Torvalds *
1361da177e4SLinus Torvalds * When the page @dest_pages[@xpage] is completed, @xpage_done is set to 1.
1371da177e4SLinus Torvalds * If xpage is -1 or @xpage has not been completed, @xpage_done is not modified.
1381da177e4SLinus Torvalds *
1391da177e4SLinus Torvalds * @cb_start is a pointer to the compression block which needs decompressing
1401da177e4SLinus Torvalds * and @cb_size is the size of @cb_start in bytes (8-64kiB).
1411da177e4SLinus Torvalds *
1421da177e4SLinus Torvalds * Return 0 if success or -EOVERFLOW on error in the compressed stream.
1431da177e4SLinus Torvalds * @xpage_done indicates whether the target page (@dest_pages[@xpage]) was
1441da177e4SLinus Torvalds * completed during the decompression of the compression block (@cb_start).
1451da177e4SLinus Torvalds *
146ea1754a0SKirill A. Shutemov * Warning: This function *REQUIRES* PAGE_SIZE >= 4096 or it will blow up
1471da177e4SLinus Torvalds * unpredicatbly! You have been warned!
1481da177e4SLinus Torvalds *
1491da177e4SLinus Torvalds * Note to hackers: This function may not sleep until it has finished accessing
1501da177e4SLinus Torvalds * the compression block @cb_start as it is a per-CPU buffer.
1511da177e4SLinus Torvalds */
ntfs_decompress(struct page * dest_pages[],int completed_pages[],int * dest_index,int * dest_ofs,const int dest_max_index,const int dest_max_ofs,const int xpage,char * xpage_done,u8 * const cb_start,const u32 cb_size,const loff_t i_size,const s64 initialized_size)1522c27ce91SKees Cook static int ntfs_decompress(struct page *dest_pages[], int completed_pages[],
1532c27ce91SKees Cook int *dest_index, int *dest_ofs, const int dest_max_index,
1542c27ce91SKees Cook const int dest_max_ofs, const int xpage, char *xpage_done,
1552c27ce91SKees Cook u8 *const cb_start, const u32 cb_size, const loff_t i_size,
15636763677SAnton Altaparmakov const s64 initialized_size)
1571da177e4SLinus Torvalds {
1581da177e4SLinus Torvalds /*
1591da177e4SLinus Torvalds * Pointers into the compressed data, i.e. the compression block (cb),
1601da177e4SLinus Torvalds * and the therein contained sub-blocks (sb).
1611da177e4SLinus Torvalds */
1621da177e4SLinus Torvalds u8 *cb_end = cb_start + cb_size; /* End of cb. */
1631da177e4SLinus Torvalds u8 *cb = cb_start; /* Current position in cb. */
164*04faa6cfSColin Ian King u8 *cb_sb_start; /* Beginning of the current sb in the cb. */
1651da177e4SLinus Torvalds u8 *cb_sb_end; /* End of current sb / beginning of next sb. */
1661da177e4SLinus Torvalds
1671da177e4SLinus Torvalds /* Variables for uncompressed data / destination. */
1681da177e4SLinus Torvalds struct page *dp; /* Current destination page being worked on. */
1691da177e4SLinus Torvalds u8 *dp_addr; /* Current pointer into dp. */
1701da177e4SLinus Torvalds u8 *dp_sb_start; /* Start of current sub-block in dp. */
1711da177e4SLinus Torvalds u8 *dp_sb_end; /* End of current sb in dp (dp_sb_start +
1721da177e4SLinus Torvalds NTFS_SB_SIZE). */
1731da177e4SLinus Torvalds u16 do_sb_start; /* @dest_ofs when starting this sub-block. */
1741da177e4SLinus Torvalds u16 do_sb_end; /* @dest_ofs of end of this sb (do_sb_start +
1751da177e4SLinus Torvalds NTFS_SB_SIZE). */
1761da177e4SLinus Torvalds
1771da177e4SLinus Torvalds /* Variables for tag and token parsing. */
1781da177e4SLinus Torvalds u8 tag; /* Current tag. */
1791da177e4SLinus Torvalds int token; /* Loop counter for the eight tokens in tag. */
1801da177e4SLinus Torvalds int nr_completed_pages = 0;
1811da177e4SLinus Torvalds
1821da177e4SLinus Torvalds /* Default error code. */
1831da177e4SLinus Torvalds int err = -EOVERFLOW;
1841da177e4SLinus Torvalds
1851da177e4SLinus Torvalds ntfs_debug("Entering, cb_size = 0x%x.", cb_size);
1861da177e4SLinus Torvalds do_next_sb:
1871da177e4SLinus Torvalds ntfs_debug("Beginning sub-block at offset = 0x%zx in the cb.",
1881da177e4SLinus Torvalds cb - cb_start);
1891da177e4SLinus Torvalds /*
1901da177e4SLinus Torvalds * Have we reached the end of the compression block or the end of the
1911da177e4SLinus Torvalds * decompressed data? The latter can happen for example if the current
1921da177e4SLinus Torvalds * position in the compression block is one byte before its end so the
1931da177e4SLinus Torvalds * first two checks do not detect it.
1941da177e4SLinus Torvalds */
1951da177e4SLinus Torvalds if (cb == cb_end || !le16_to_cpup((le16*)cb) ||
1961da177e4SLinus Torvalds (*dest_index == dest_max_index &&
1971da177e4SLinus Torvalds *dest_ofs == dest_max_ofs)) {
1981da177e4SLinus Torvalds int i;
1991da177e4SLinus Torvalds
2001da177e4SLinus Torvalds ntfs_debug("Completed. Returning success (0).");
2011da177e4SLinus Torvalds err = 0;
2021da177e4SLinus Torvalds return_error:
2031da177e4SLinus Torvalds /* We can sleep from now on, so we drop lock. */
2041da177e4SLinus Torvalds spin_unlock(&ntfs_cb_lock);
2051da177e4SLinus Torvalds /* Second stage: finalize completed pages. */
2061da177e4SLinus Torvalds if (nr_completed_pages > 0) {
2071da177e4SLinus Torvalds for (i = 0; i < nr_completed_pages; i++) {
2081da177e4SLinus Torvalds int di = completed_pages[i];
2091da177e4SLinus Torvalds
2101da177e4SLinus Torvalds dp = dest_pages[di];
2111da177e4SLinus Torvalds /*
2121da177e4SLinus Torvalds * If we are outside the initialized size, zero
2131da177e4SLinus Torvalds * the out of bounds page range.
2141da177e4SLinus Torvalds */
21536763677SAnton Altaparmakov handle_bounds_compressed_page(dp, i_size,
21636763677SAnton Altaparmakov initialized_size);
2171da177e4SLinus Torvalds flush_dcache_page(dp);
2181da177e4SLinus Torvalds kunmap(dp);
2191da177e4SLinus Torvalds SetPageUptodate(dp);
2201da177e4SLinus Torvalds unlock_page(dp);
2211da177e4SLinus Torvalds if (di == xpage)
2221da177e4SLinus Torvalds *xpage_done = 1;
2231da177e4SLinus Torvalds else
22409cbfeafSKirill A. Shutemov put_page(dp);
2251da177e4SLinus Torvalds dest_pages[di] = NULL;
2261da177e4SLinus Torvalds }
2271da177e4SLinus Torvalds }
2281da177e4SLinus Torvalds return err;
2291da177e4SLinus Torvalds }
2301da177e4SLinus Torvalds
2311da177e4SLinus Torvalds /* Setup offsets for the current sub-block destination. */
2321da177e4SLinus Torvalds do_sb_start = *dest_ofs;
2331da177e4SLinus Torvalds do_sb_end = do_sb_start + NTFS_SB_SIZE;
2341da177e4SLinus Torvalds
2351da177e4SLinus Torvalds /* Check that we are still within allowed boundaries. */
2361da177e4SLinus Torvalds if (*dest_index == dest_max_index && do_sb_end > dest_max_ofs)
2371da177e4SLinus Torvalds goto return_overflow;
2381da177e4SLinus Torvalds
2391da177e4SLinus Torvalds /* Does the minimum size of a compressed sb overflow valid range? */
2401da177e4SLinus Torvalds if (cb + 6 > cb_end)
2411da177e4SLinus Torvalds goto return_overflow;
2421da177e4SLinus Torvalds
2431da177e4SLinus Torvalds /* Setup the current sub-block source pointers and validate range. */
2441da177e4SLinus Torvalds cb_sb_start = cb;
2451da177e4SLinus Torvalds cb_sb_end = cb_sb_start + (le16_to_cpup((le16*)cb) & NTFS_SB_SIZE_MASK)
2461da177e4SLinus Torvalds + 3;
2471da177e4SLinus Torvalds if (cb_sb_end > cb_end)
2481da177e4SLinus Torvalds goto return_overflow;
2491da177e4SLinus Torvalds
2501da177e4SLinus Torvalds /* Get the current destination page. */
2511da177e4SLinus Torvalds dp = dest_pages[*dest_index];
2521da177e4SLinus Torvalds if (!dp) {
2531da177e4SLinus Torvalds /* No page present. Skip decompression of this sub-block. */
2541da177e4SLinus Torvalds cb = cb_sb_end;
2551da177e4SLinus Torvalds
2561da177e4SLinus Torvalds /* Advance destination position to next sub-block. */
25709cbfeafSKirill A. Shutemov *dest_ofs = (*dest_ofs + NTFS_SB_SIZE) & ~PAGE_MASK;
2581da177e4SLinus Torvalds if (!*dest_ofs && (++*dest_index > dest_max_index))
2591da177e4SLinus Torvalds goto return_overflow;
2601da177e4SLinus Torvalds goto do_next_sb;
2611da177e4SLinus Torvalds }
2621da177e4SLinus Torvalds
2631da177e4SLinus Torvalds /* We have a valid destination page. Setup the destination pointers. */
2641da177e4SLinus Torvalds dp_addr = (u8*)page_address(dp) + do_sb_start;
2651da177e4SLinus Torvalds
2661da177e4SLinus Torvalds /* Now, we are ready to process the current sub-block (sb). */
2671da177e4SLinus Torvalds if (!(le16_to_cpup((le16*)cb) & NTFS_SB_IS_COMPRESSED)) {
2681da177e4SLinus Torvalds ntfs_debug("Found uncompressed sub-block.");
2691da177e4SLinus Torvalds /* This sb is not compressed, just copy it into destination. */
2701da177e4SLinus Torvalds
2711da177e4SLinus Torvalds /* Advance source position to first data byte. */
2721da177e4SLinus Torvalds cb += 2;
2731da177e4SLinus Torvalds
2741da177e4SLinus Torvalds /* An uncompressed sb must be full size. */
2751da177e4SLinus Torvalds if (cb_sb_end - cb != NTFS_SB_SIZE)
2761da177e4SLinus Torvalds goto return_overflow;
2771da177e4SLinus Torvalds
2781da177e4SLinus Torvalds /* Copy the block and advance the source position. */
2791da177e4SLinus Torvalds memcpy(dp_addr, cb, NTFS_SB_SIZE);
2801da177e4SLinus Torvalds cb += NTFS_SB_SIZE;
2811da177e4SLinus Torvalds
2821da177e4SLinus Torvalds /* Advance destination position to next sub-block. */
2831da177e4SLinus Torvalds *dest_ofs += NTFS_SB_SIZE;
28409cbfeafSKirill A. Shutemov if (!(*dest_ofs &= ~PAGE_MASK)) {
2851da177e4SLinus Torvalds finalize_page:
2861da177e4SLinus Torvalds /*
2871da177e4SLinus Torvalds * First stage: add current page index to array of
2881da177e4SLinus Torvalds * completed pages.
2891da177e4SLinus Torvalds */
2901da177e4SLinus Torvalds completed_pages[nr_completed_pages++] = *dest_index;
2911da177e4SLinus Torvalds if (++*dest_index > dest_max_index)
2921da177e4SLinus Torvalds goto return_overflow;
2931da177e4SLinus Torvalds }
2941da177e4SLinus Torvalds goto do_next_sb;
2951da177e4SLinus Torvalds }
2961da177e4SLinus Torvalds ntfs_debug("Found compressed sub-block.");
2971da177e4SLinus Torvalds /* This sb is compressed, decompress it into destination. */
2981da177e4SLinus Torvalds
2991da177e4SLinus Torvalds /* Setup destination pointers. */
3001da177e4SLinus Torvalds dp_sb_start = dp_addr;
3011da177e4SLinus Torvalds dp_sb_end = dp_sb_start + NTFS_SB_SIZE;
3021da177e4SLinus Torvalds
3031da177e4SLinus Torvalds /* Forward to the first tag in the sub-block. */
3041da177e4SLinus Torvalds cb += 2;
3051da177e4SLinus Torvalds do_next_tag:
3061da177e4SLinus Torvalds if (cb == cb_sb_end) {
3071da177e4SLinus Torvalds /* Check if the decompressed sub-block was not full-length. */
3081da177e4SLinus Torvalds if (dp_addr < dp_sb_end) {
3091da177e4SLinus Torvalds int nr_bytes = do_sb_end - *dest_ofs;
3101da177e4SLinus Torvalds
3111da177e4SLinus Torvalds ntfs_debug("Filling incomplete sub-block with "
3121da177e4SLinus Torvalds "zeroes.");
3131da177e4SLinus Torvalds /* Zero remainder and update destination position. */
3141da177e4SLinus Torvalds memset(dp_addr, 0, nr_bytes);
3151da177e4SLinus Torvalds *dest_ofs += nr_bytes;
3161da177e4SLinus Torvalds }
3171da177e4SLinus Torvalds /* We have finished the current sub-block. */
31809cbfeafSKirill A. Shutemov if (!(*dest_ofs &= ~PAGE_MASK))
3191da177e4SLinus Torvalds goto finalize_page;
3201da177e4SLinus Torvalds goto do_next_sb;
3211da177e4SLinus Torvalds }
3221da177e4SLinus Torvalds
3231da177e4SLinus Torvalds /* Check we are still in range. */
3241da177e4SLinus Torvalds if (cb > cb_sb_end || dp_addr > dp_sb_end)
3251da177e4SLinus Torvalds goto return_overflow;
3261da177e4SLinus Torvalds
3271da177e4SLinus Torvalds /* Get the next tag and advance to first token. */
3281da177e4SLinus Torvalds tag = *cb++;
3291da177e4SLinus Torvalds
3301da177e4SLinus Torvalds /* Parse the eight tokens described by the tag. */
3311da177e4SLinus Torvalds for (token = 0; token < 8; token++, tag >>= 1) {
3321da177e4SLinus Torvalds u16 lg, pt, length, max_non_overlap;
3331da177e4SLinus Torvalds register u16 i;
3341da177e4SLinus Torvalds u8 *dp_back_addr;
3351da177e4SLinus Torvalds
3361da177e4SLinus Torvalds /* Check if we are done / still in range. */
3371da177e4SLinus Torvalds if (cb >= cb_sb_end || dp_addr > dp_sb_end)
3381da177e4SLinus Torvalds break;
3391da177e4SLinus Torvalds
3401da177e4SLinus Torvalds /* Determine token type and parse appropriately.*/
3411da177e4SLinus Torvalds if ((tag & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) {
3421da177e4SLinus Torvalds /*
3431da177e4SLinus Torvalds * We have a symbol token, copy the symbol across, and
3441da177e4SLinus Torvalds * advance the source and destination positions.
3451da177e4SLinus Torvalds */
3461da177e4SLinus Torvalds *dp_addr++ = *cb++;
3471da177e4SLinus Torvalds ++*dest_ofs;
3481da177e4SLinus Torvalds
3491da177e4SLinus Torvalds /* Continue with the next token. */
3501da177e4SLinus Torvalds continue;
3511da177e4SLinus Torvalds }
3521da177e4SLinus Torvalds
3531da177e4SLinus Torvalds /*
3541da177e4SLinus Torvalds * We have a phrase token. Make sure it is not the first tag in
3551da177e4SLinus Torvalds * the sb as this is illegal and would confuse the code below.
3561da177e4SLinus Torvalds */
3571da177e4SLinus Torvalds if (dp_addr == dp_sb_start)
3581da177e4SLinus Torvalds goto return_overflow;
3591da177e4SLinus Torvalds
3601da177e4SLinus Torvalds /*
3611da177e4SLinus Torvalds * Determine the number of bytes to go back (p) and the number
3621da177e4SLinus Torvalds * of bytes to copy (l). We use an optimized algorithm in which
3631da177e4SLinus Torvalds * we first calculate log2(current destination position in sb),
3641da177e4SLinus Torvalds * which allows determination of l and p in O(1) rather than
3651da177e4SLinus Torvalds * O(n). We just need an arch-optimized log2() function now.
3661da177e4SLinus Torvalds */
3671da177e4SLinus Torvalds lg = 0;
3681da177e4SLinus Torvalds for (i = *dest_ofs - do_sb_start - 1; i >= 0x10; i >>= 1)
3691da177e4SLinus Torvalds lg++;
3701da177e4SLinus Torvalds
3711da177e4SLinus Torvalds /* Get the phrase token into i. */
3721da177e4SLinus Torvalds pt = le16_to_cpup((le16*)cb);
3731da177e4SLinus Torvalds
3741da177e4SLinus Torvalds /*
3751da177e4SLinus Torvalds * Calculate starting position of the byte sequence in
3761da177e4SLinus Torvalds * the destination using the fact that p = (pt >> (12 - lg)) + 1
3771da177e4SLinus Torvalds * and make sure we don't go too far back.
3781da177e4SLinus Torvalds */
3791da177e4SLinus Torvalds dp_back_addr = dp_addr - (pt >> (12 - lg)) - 1;
3801da177e4SLinus Torvalds if (dp_back_addr < dp_sb_start)
3811da177e4SLinus Torvalds goto return_overflow;
3821da177e4SLinus Torvalds
3831da177e4SLinus Torvalds /* Now calculate the length of the byte sequence. */
3841da177e4SLinus Torvalds length = (pt & (0xfff >> lg)) + 3;
3851da177e4SLinus Torvalds
3861da177e4SLinus Torvalds /* Advance destination position and verify it is in range. */
3871da177e4SLinus Torvalds *dest_ofs += length;
3881da177e4SLinus Torvalds if (*dest_ofs > do_sb_end)
3891da177e4SLinus Torvalds goto return_overflow;
3901da177e4SLinus Torvalds
3911da177e4SLinus Torvalds /* The number of non-overlapping bytes. */
3921da177e4SLinus Torvalds max_non_overlap = dp_addr - dp_back_addr;
3931da177e4SLinus Torvalds
3941da177e4SLinus Torvalds if (length <= max_non_overlap) {
3951da177e4SLinus Torvalds /* The byte sequence doesn't overlap, just copy it. */
3961da177e4SLinus Torvalds memcpy(dp_addr, dp_back_addr, length);
3971da177e4SLinus Torvalds
3981da177e4SLinus Torvalds /* Advance destination pointer. */
3991da177e4SLinus Torvalds dp_addr += length;
4001da177e4SLinus Torvalds } else {
4011da177e4SLinus Torvalds /*
4021da177e4SLinus Torvalds * The byte sequence does overlap, copy non-overlapping
4031da177e4SLinus Torvalds * part and then do a slow byte by byte copy for the
4041da177e4SLinus Torvalds * overlapping part. Also, advance the destination
4051da177e4SLinus Torvalds * pointer.
4061da177e4SLinus Torvalds */
4071da177e4SLinus Torvalds memcpy(dp_addr, dp_back_addr, max_non_overlap);
4081da177e4SLinus Torvalds dp_addr += max_non_overlap;
4091da177e4SLinus Torvalds dp_back_addr += max_non_overlap;
4101da177e4SLinus Torvalds length -= max_non_overlap;
4111da177e4SLinus Torvalds while (length--)
4121da177e4SLinus Torvalds *dp_addr++ = *dp_back_addr++;
4131da177e4SLinus Torvalds }
4141da177e4SLinus Torvalds
4151da177e4SLinus Torvalds /* Advance source position and continue with the next token. */
4161da177e4SLinus Torvalds cb += 2;
4171da177e4SLinus Torvalds }
4181da177e4SLinus Torvalds
4191da177e4SLinus Torvalds /* No tokens left in the current tag. Continue with the next tag. */
4201da177e4SLinus Torvalds goto do_next_tag;
4211da177e4SLinus Torvalds
4221da177e4SLinus Torvalds return_overflow:
4231da177e4SLinus Torvalds ntfs_error(NULL, "Failed. Returning -EOVERFLOW.");
4241da177e4SLinus Torvalds goto return_error;
4251da177e4SLinus Torvalds }
4261da177e4SLinus Torvalds
4271da177e4SLinus Torvalds /**
4281da177e4SLinus Torvalds * ntfs_read_compressed_block - read a compressed block into the page cache
4291da177e4SLinus Torvalds * @page: locked page in the compression block(s) we need to read
4301da177e4SLinus Torvalds *
4311da177e4SLinus Torvalds * When we are called the page has already been verified to be locked and the
4321da177e4SLinus Torvalds * attribute is known to be non-resident, not encrypted, but compressed.
4331da177e4SLinus Torvalds *
4341da177e4SLinus Torvalds * 1. Determine which compression block(s) @page is in.
4351da177e4SLinus Torvalds * 2. Get hold of all pages corresponding to this/these compression block(s).
4361da177e4SLinus Torvalds * 3. Read the (first) compression block.
4371da177e4SLinus Torvalds * 4. Decompress it into the corresponding pages.
4381da177e4SLinus Torvalds * 5. Throw the compressed data away and proceed to 3. for the next compression
4391da177e4SLinus Torvalds * block or return success if no more compression blocks left.
4401da177e4SLinus Torvalds *
4411da177e4SLinus Torvalds * Warning: We have to be careful what we do about existing pages. They might
4421da177e4SLinus Torvalds * have been written to so that we would lose data if we were to just overwrite
4431da177e4SLinus Torvalds * them with the out-of-date uncompressed data.
4441da177e4SLinus Torvalds *
445ea1754a0SKirill A. Shutemov * FIXME: For PAGE_SIZE > cb_size we are not doing the Right Thing(TM) at
4461da177e4SLinus Torvalds * the end of the file I think. We need to detect this case and zero the out
4471da177e4SLinus Torvalds * of bounds remainder of the page in question and mark it as handled. At the
4481da177e4SLinus Torvalds * moment we would just return -EIO on such a page. This bug will only become
4491da177e4SLinus Torvalds * apparent if pages are above 8kiB and the NTFS volume only uses 512 byte
4501da177e4SLinus Torvalds * clusters so is probably not going to be seen by anyone. Still this should
4511da177e4SLinus Torvalds * be fixed. (AIA)
4521da177e4SLinus Torvalds *
453ea1754a0SKirill A. Shutemov * FIXME: Again for PAGE_SIZE > cb_size we are screwing up both in
4541da177e4SLinus Torvalds * handling sparse and compressed cbs. (AIA)
4551da177e4SLinus Torvalds *
4561da177e4SLinus Torvalds * FIXME: At the moment we don't do any zeroing out in the case that
4571da177e4SLinus Torvalds * initialized_size is less than data_size. This should be safe because of the
4581da177e4SLinus Torvalds * nature of the compression algorithm used. Just in case we check and output
4591da177e4SLinus Torvalds * an error message in read inode if the two sizes are not equal for a
4601da177e4SLinus Torvalds * compressed file. (AIA)
4611da177e4SLinus Torvalds */
ntfs_read_compressed_block(struct page * page)4621da177e4SLinus Torvalds int ntfs_read_compressed_block(struct page *page)
4631da177e4SLinus Torvalds {
46436763677SAnton Altaparmakov loff_t i_size;
46536763677SAnton Altaparmakov s64 initialized_size;
4661da177e4SLinus Torvalds struct address_space *mapping = page->mapping;
4671da177e4SLinus Torvalds ntfs_inode *ni = NTFS_I(mapping->host);
4681da177e4SLinus Torvalds ntfs_volume *vol = ni->vol;
4691da177e4SLinus Torvalds struct super_block *sb = vol->sb;
4701da177e4SLinus Torvalds runlist_element *rl;
47136763677SAnton Altaparmakov unsigned long flags, block_size = sb->s_blocksize;
4721da177e4SLinus Torvalds unsigned char block_size_bits = sb->s_blocksize_bits;
4731da177e4SLinus Torvalds u8 *cb, *cb_pos, *cb_end;
4741da177e4SLinus Torvalds struct buffer_head **bhs;
4751da177e4SLinus Torvalds unsigned long offset, index = page->index;
4761da177e4SLinus Torvalds u32 cb_size = ni->itype.compressed.block_size;
4771da177e4SLinus Torvalds u64 cb_size_mask = cb_size - 1UL;
4781da177e4SLinus Torvalds VCN vcn;
4791da177e4SLinus Torvalds LCN lcn;
480ea1754a0SKirill A. Shutemov /* The first wanted vcn (minimum alignment is PAGE_SIZE). */
48109cbfeafSKirill A. Shutemov VCN start_vcn = (((s64)index << PAGE_SHIFT) & ~cb_size_mask) >>
4821da177e4SLinus Torvalds vol->cluster_size_bits;
4831da177e4SLinus Torvalds /*
48425985edcSLucas De Marchi * The first vcn after the last wanted vcn (minimum alignment is again
485ea1754a0SKirill A. Shutemov * PAGE_SIZE.
4861da177e4SLinus Torvalds */
48709cbfeafSKirill A. Shutemov VCN end_vcn = ((((s64)(index + 1UL) << PAGE_SHIFT) + cb_size - 1)
4881da177e4SLinus Torvalds & ~cb_size_mask) >> vol->cluster_size_bits;
4891da177e4SLinus Torvalds /* Number of compression blocks (cbs) in the wanted vcn range. */
4901da177e4SLinus Torvalds unsigned int nr_cbs = (end_vcn - start_vcn) << vol->cluster_size_bits
4911da177e4SLinus Torvalds >> ni->itype.compressed.block_size_bits;
4921da177e4SLinus Torvalds /*
4931da177e4SLinus Torvalds * Number of pages required to store the uncompressed data from all
4941da177e4SLinus Torvalds * compression blocks (cbs) overlapping @page. Due to alignment
4951da177e4SLinus Torvalds * guarantees of start_vcn and end_vcn, no need to round up here.
4961da177e4SLinus Torvalds */
4971da177e4SLinus Torvalds unsigned int nr_pages = (end_vcn - start_vcn) <<
49809cbfeafSKirill A. Shutemov vol->cluster_size_bits >> PAGE_SHIFT;
4991da177e4SLinus Torvalds unsigned int xpage, max_page, cur_page, cur_ofs, i;
5001da177e4SLinus Torvalds unsigned int cb_clusters, cb_max_ofs;
5011da177e4SLinus Torvalds int block, max_block, cb_max_page, bhs_size, nr_bhs, err = 0;
5021da177e4SLinus Torvalds struct page **pages;
5032c27ce91SKees Cook int *completed_pages;
5041da177e4SLinus Torvalds unsigned char xpage_done = 0;
5051da177e4SLinus Torvalds
5061da177e4SLinus Torvalds ntfs_debug("Entering, page->index = 0x%lx, cb_size = 0x%x, nr_pages = "
5071da177e4SLinus Torvalds "%i.", index, cb_size, nr_pages);
5081da177e4SLinus Torvalds /*
5091da177e4SLinus Torvalds * Bad things happen if we get here for anything that is not an
5101da177e4SLinus Torvalds * unnamed $DATA attribute.
5111da177e4SLinus Torvalds */
5121da177e4SLinus Torvalds BUG_ON(ni->type != AT_DATA);
5131da177e4SLinus Torvalds BUG_ON(ni->name_len);
5141da177e4SLinus Torvalds
5156da2ec56SKees Cook pages = kmalloc_array(nr_pages, sizeof(struct page *), GFP_NOFS);
5162c27ce91SKees Cook completed_pages = kmalloc_array(nr_pages + 1, sizeof(int), GFP_NOFS);
5171da177e4SLinus Torvalds
5181da177e4SLinus Torvalds /* Allocate memory to store the buffer heads we need. */
5191da177e4SLinus Torvalds bhs_size = cb_size / block_size * sizeof(struct buffer_head *);
5201da177e4SLinus Torvalds bhs = kmalloc(bhs_size, GFP_NOFS);
5211da177e4SLinus Torvalds
5222c27ce91SKees Cook if (unlikely(!pages || !bhs || !completed_pages)) {
5231da177e4SLinus Torvalds kfree(bhs);
5241da177e4SLinus Torvalds kfree(pages);
5252c27ce91SKees Cook kfree(completed_pages);
5261da177e4SLinus Torvalds unlock_page(page);
5271da177e4SLinus Torvalds ntfs_error(vol->sb, "Failed to allocate internal buffers.");
5281da177e4SLinus Torvalds return -ENOMEM;
5291da177e4SLinus Torvalds }
5301da177e4SLinus Torvalds
5311da177e4SLinus Torvalds /*
5321da177e4SLinus Torvalds * We have already been given one page, this is the one we must do.
5331da177e4SLinus Torvalds * Once again, the alignment guarantees keep it simple.
5341da177e4SLinus Torvalds */
53509cbfeafSKirill A. Shutemov offset = start_vcn << vol->cluster_size_bits >> PAGE_SHIFT;
5361da177e4SLinus Torvalds xpage = index - offset;
5371da177e4SLinus Torvalds pages[xpage] = page;
5381da177e4SLinus Torvalds /*
5391da177e4SLinus Torvalds * The remaining pages need to be allocated and inserted into the page
5401da177e4SLinus Torvalds * cache, alignment guarantees keep all the below much simpler. (-8
5411da177e4SLinus Torvalds */
54236763677SAnton Altaparmakov read_lock_irqsave(&ni->size_lock, flags);
54336763677SAnton Altaparmakov i_size = i_size_read(VFS_I(ni));
54436763677SAnton Altaparmakov initialized_size = ni->initialized_size;
54536763677SAnton Altaparmakov read_unlock_irqrestore(&ni->size_lock, flags);
54609cbfeafSKirill A. Shutemov max_page = ((i_size + PAGE_SIZE - 1) >> PAGE_SHIFT) -
54736763677SAnton Altaparmakov offset;
548ebab8990SAnton Altaparmakov /* Is the page fully outside i_size? (truncate in progress) */
549ebab8990SAnton Altaparmakov if (xpage >= max_page) {
550ebab8990SAnton Altaparmakov kfree(bhs);
551ebab8990SAnton Altaparmakov kfree(pages);
5522c27ce91SKees Cook kfree(completed_pages);
55309cbfeafSKirill A. Shutemov zero_user(page, 0, PAGE_SIZE);
554ebab8990SAnton Altaparmakov ntfs_debug("Compressed read outside i_size - truncated?");
555ebab8990SAnton Altaparmakov SetPageUptodate(page);
556ebab8990SAnton Altaparmakov unlock_page(page);
557ebab8990SAnton Altaparmakov return 0;
558ebab8990SAnton Altaparmakov }
5591da177e4SLinus Torvalds if (nr_pages < max_page)
5601da177e4SLinus Torvalds max_page = nr_pages;
5611da177e4SLinus Torvalds for (i = 0; i < max_page; i++, offset++) {
5621da177e4SLinus Torvalds if (i != xpage)
5631da177e4SLinus Torvalds pages[i] = grab_cache_page_nowait(mapping, offset);
5641da177e4SLinus Torvalds page = pages[i];
5651da177e4SLinus Torvalds if (page) {
5661da177e4SLinus Torvalds /*
5671da177e4SLinus Torvalds * We only (re)read the page if it isn't already read
5681da177e4SLinus Torvalds * in and/or dirty or we would be losing data or at
5691da177e4SLinus Torvalds * least wasting our time.
5701da177e4SLinus Torvalds */
5711da177e4SLinus Torvalds if (!PageDirty(page) && (!PageUptodate(page) ||
5721da177e4SLinus Torvalds PageError(page))) {
5731da177e4SLinus Torvalds ClearPageError(page);
5741da177e4SLinus Torvalds kmap(page);
5751da177e4SLinus Torvalds continue;
5761da177e4SLinus Torvalds }
5771da177e4SLinus Torvalds unlock_page(page);
57809cbfeafSKirill A. Shutemov put_page(page);
5791da177e4SLinus Torvalds pages[i] = NULL;
5801da177e4SLinus Torvalds }
5811da177e4SLinus Torvalds }
5821da177e4SLinus Torvalds
5831da177e4SLinus Torvalds /*
5841da177e4SLinus Torvalds * We have the runlist, and all the destination pages we need to fill.
5851da177e4SLinus Torvalds * Now read the first compression block.
5861da177e4SLinus Torvalds */
5871da177e4SLinus Torvalds cur_page = 0;
5881da177e4SLinus Torvalds cur_ofs = 0;
5891da177e4SLinus Torvalds cb_clusters = ni->itype.compressed.block_clusters;
5901da177e4SLinus Torvalds do_next_cb:
5911da177e4SLinus Torvalds nr_cbs--;
5921da177e4SLinus Torvalds nr_bhs = 0;
5931da177e4SLinus Torvalds
5941da177e4SLinus Torvalds /* Read all cb buffer heads one cluster at a time. */
5951da177e4SLinus Torvalds rl = NULL;
5961da177e4SLinus Torvalds for (vcn = start_vcn, start_vcn += cb_clusters; vcn < start_vcn;
5971da177e4SLinus Torvalds vcn++) {
598c49c3111SRichard Knutsson bool is_retry = false;
5991da177e4SLinus Torvalds
6001da177e4SLinus Torvalds if (!rl) {
6011da177e4SLinus Torvalds lock_retry_remap:
6021da177e4SLinus Torvalds down_read(&ni->runlist.lock);
6031da177e4SLinus Torvalds rl = ni->runlist.rl;
6041da177e4SLinus Torvalds }
6051da177e4SLinus Torvalds if (likely(rl != NULL)) {
6061da177e4SLinus Torvalds /* Seek to element containing target vcn. */
6071da177e4SLinus Torvalds while (rl->length && rl[1].vcn <= vcn)
6081da177e4SLinus Torvalds rl++;
6091da177e4SLinus Torvalds lcn = ntfs_rl_vcn_to_lcn(rl, vcn);
6101da177e4SLinus Torvalds } else
6111da177e4SLinus Torvalds lcn = LCN_RL_NOT_MAPPED;
6121da177e4SLinus Torvalds ntfs_debug("Reading vcn = 0x%llx, lcn = 0x%llx.",
6131da177e4SLinus Torvalds (unsigned long long)vcn,
6141da177e4SLinus Torvalds (unsigned long long)lcn);
6151da177e4SLinus Torvalds if (lcn < 0) {
6161da177e4SLinus Torvalds /*
6171da177e4SLinus Torvalds * When we reach the first sparse cluster we have
6181da177e4SLinus Torvalds * finished with the cb.
6191da177e4SLinus Torvalds */
6201da177e4SLinus Torvalds if (lcn == LCN_HOLE)
6211da177e4SLinus Torvalds break;
6221da177e4SLinus Torvalds if (is_retry || lcn != LCN_RL_NOT_MAPPED)
6231da177e4SLinus Torvalds goto rl_err;
624c49c3111SRichard Knutsson is_retry = true;
6251da177e4SLinus Torvalds /*
6261da177e4SLinus Torvalds * Attempt to map runlist, dropping lock for the
6271da177e4SLinus Torvalds * duration.
6281da177e4SLinus Torvalds */
6291da177e4SLinus Torvalds up_read(&ni->runlist.lock);
6301da177e4SLinus Torvalds if (!ntfs_map_runlist(ni, vcn))
6311da177e4SLinus Torvalds goto lock_retry_remap;
6321da177e4SLinus Torvalds goto map_rl_err;
6331da177e4SLinus Torvalds }
6341da177e4SLinus Torvalds block = lcn << vol->cluster_size_bits >> block_size_bits;
6351da177e4SLinus Torvalds /* Read the lcn from device in chunks of block_size bytes. */
6361da177e4SLinus Torvalds max_block = block + (vol->cluster_size >> block_size_bits);
6371da177e4SLinus Torvalds do {
6381da177e4SLinus Torvalds ntfs_debug("block = 0x%x.", block);
6391da177e4SLinus Torvalds if (unlikely(!(bhs[nr_bhs] = sb_getblk(sb, block))))
6401da177e4SLinus Torvalds goto getblk_err;
6411da177e4SLinus Torvalds nr_bhs++;
6421da177e4SLinus Torvalds } while (++block < max_block);
6431da177e4SLinus Torvalds }
6441da177e4SLinus Torvalds
6451da177e4SLinus Torvalds /* Release the lock if we took it. */
6461da177e4SLinus Torvalds if (rl)
6471da177e4SLinus Torvalds up_read(&ni->runlist.lock);
6481da177e4SLinus Torvalds
6491da177e4SLinus Torvalds /* Setup and initiate io on all buffer heads. */
6501da177e4SLinus Torvalds for (i = 0; i < nr_bhs; i++) {
6511da177e4SLinus Torvalds struct buffer_head *tbh = bhs[i];
6521da177e4SLinus Torvalds
653ca5de404SNick Piggin if (!trylock_buffer(tbh))
6541da177e4SLinus Torvalds continue;
6551da177e4SLinus Torvalds if (unlikely(buffer_uptodate(tbh))) {
6561da177e4SLinus Torvalds unlock_buffer(tbh);
6571da177e4SLinus Torvalds continue;
6581da177e4SLinus Torvalds }
6591da177e4SLinus Torvalds get_bh(tbh);
6601da177e4SLinus Torvalds tbh->b_end_io = end_buffer_read_sync;
6611420c4a5SBart Van Assche submit_bh(REQ_OP_READ, tbh);
6621da177e4SLinus Torvalds }
6631da177e4SLinus Torvalds
6641da177e4SLinus Torvalds /* Wait for io completion on all buffer heads. */
6651da177e4SLinus Torvalds for (i = 0; i < nr_bhs; i++) {
6661da177e4SLinus Torvalds struct buffer_head *tbh = bhs[i];
6671da177e4SLinus Torvalds
6681da177e4SLinus Torvalds if (buffer_uptodate(tbh))
6691da177e4SLinus Torvalds continue;
6701da177e4SLinus Torvalds wait_on_buffer(tbh);
6711da177e4SLinus Torvalds /*
6721da177e4SLinus Torvalds * We need an optimization barrier here, otherwise we start
6731da177e4SLinus Torvalds * hitting the below fixup code when accessing a loopback
6741da177e4SLinus Torvalds * mounted ntfs partition. This indicates either there is a
6751da177e4SLinus Torvalds * race condition in the loop driver or, more likely, gcc
6761da177e4SLinus Torvalds * overoptimises the code without the barrier and it doesn't
6771da177e4SLinus Torvalds * do the Right Thing(TM).
6781da177e4SLinus Torvalds */
6791da177e4SLinus Torvalds barrier();
6801da177e4SLinus Torvalds if (unlikely(!buffer_uptodate(tbh))) {
6811da177e4SLinus Torvalds ntfs_warning(vol->sb, "Buffer is unlocked but not "
6821da177e4SLinus Torvalds "uptodate! Unplugging the disk queue "
6831da177e4SLinus Torvalds "and rescheduling.");
6841da177e4SLinus Torvalds get_bh(tbh);
6857eaceaccSJens Axboe io_schedule();
6861da177e4SLinus Torvalds put_bh(tbh);
6871da177e4SLinus Torvalds if (unlikely(!buffer_uptodate(tbh)))
6881da177e4SLinus Torvalds goto read_err;
6891da177e4SLinus Torvalds ntfs_warning(vol->sb, "Buffer is now uptodate. Good.");
6901da177e4SLinus Torvalds }
6911da177e4SLinus Torvalds }
6921da177e4SLinus Torvalds
6931da177e4SLinus Torvalds /*
6941da177e4SLinus Torvalds * Get the compression buffer. We must not sleep any more
6951da177e4SLinus Torvalds * until we are finished with it.
6961da177e4SLinus Torvalds */
6971da177e4SLinus Torvalds spin_lock(&ntfs_cb_lock);
6981da177e4SLinus Torvalds cb = ntfs_compression_buffer;
6991da177e4SLinus Torvalds
7001da177e4SLinus Torvalds BUG_ON(!cb);
7011da177e4SLinus Torvalds
7021da177e4SLinus Torvalds cb_pos = cb;
7031da177e4SLinus Torvalds cb_end = cb + cb_size;
7041da177e4SLinus Torvalds
7051da177e4SLinus Torvalds /* Copy the buffer heads into the contiguous buffer. */
7061da177e4SLinus Torvalds for (i = 0; i < nr_bhs; i++) {
7071da177e4SLinus Torvalds memcpy(cb_pos, bhs[i]->b_data, block_size);
7081da177e4SLinus Torvalds cb_pos += block_size;
7091da177e4SLinus Torvalds }
7101da177e4SLinus Torvalds
7111da177e4SLinus Torvalds /* Just a precaution. */
7121da177e4SLinus Torvalds if (cb_pos + 2 <= cb + cb_size)
7131da177e4SLinus Torvalds *(u16*)cb_pos = 0;
7141da177e4SLinus Torvalds
7151da177e4SLinus Torvalds /* Reset cb_pos back to the beginning. */
7161da177e4SLinus Torvalds cb_pos = cb;
7171da177e4SLinus Torvalds
7181da177e4SLinus Torvalds /* We now have both source (if present) and destination. */
7191da177e4SLinus Torvalds ntfs_debug("Successfully read the compression block.");
7201da177e4SLinus Torvalds
7211da177e4SLinus Torvalds /* The last page and maximum offset within it for the current cb. */
72209cbfeafSKirill A. Shutemov cb_max_page = (cur_page << PAGE_SHIFT) + cur_ofs + cb_size;
72309cbfeafSKirill A. Shutemov cb_max_ofs = cb_max_page & ~PAGE_MASK;
72409cbfeafSKirill A. Shutemov cb_max_page >>= PAGE_SHIFT;
7251da177e4SLinus Torvalds
7261da177e4SLinus Torvalds /* Catch end of file inside a compression block. */
7271da177e4SLinus Torvalds if (cb_max_page > max_page)
7281da177e4SLinus Torvalds cb_max_page = max_page;
7291da177e4SLinus Torvalds
7301da177e4SLinus Torvalds if (vcn == start_vcn - cb_clusters) {
7311da177e4SLinus Torvalds /* Sparse cb, zero out page range overlapping the cb. */
7321da177e4SLinus Torvalds ntfs_debug("Found sparse compression block.");
7331da177e4SLinus Torvalds /* We can sleep from now on, so we drop lock. */
7341da177e4SLinus Torvalds spin_unlock(&ntfs_cb_lock);
7351da177e4SLinus Torvalds if (cb_max_ofs)
7361da177e4SLinus Torvalds cb_max_page--;
7371da177e4SLinus Torvalds for (; cur_page < cb_max_page; cur_page++) {
7381da177e4SLinus Torvalds page = pages[cur_page];
7391da177e4SLinus Torvalds if (page) {
7401da177e4SLinus Torvalds if (likely(!cur_ofs))
7411da177e4SLinus Torvalds clear_page(page_address(page));
7421da177e4SLinus Torvalds else
7431da177e4SLinus Torvalds memset(page_address(page) + cur_ofs, 0,
74409cbfeafSKirill A. Shutemov PAGE_SIZE -
7451da177e4SLinus Torvalds cur_ofs);
7461da177e4SLinus Torvalds flush_dcache_page(page);
7471da177e4SLinus Torvalds kunmap(page);
7481da177e4SLinus Torvalds SetPageUptodate(page);
7491da177e4SLinus Torvalds unlock_page(page);
7501da177e4SLinus Torvalds if (cur_page == xpage)
7511da177e4SLinus Torvalds xpage_done = 1;
7521da177e4SLinus Torvalds else
75309cbfeafSKirill A. Shutemov put_page(page);
7541da177e4SLinus Torvalds pages[cur_page] = NULL;
7551da177e4SLinus Torvalds }
75609cbfeafSKirill A. Shutemov cb_pos += PAGE_SIZE - cur_ofs;
7571da177e4SLinus Torvalds cur_ofs = 0;
7581da177e4SLinus Torvalds if (cb_pos >= cb_end)
7591da177e4SLinus Torvalds break;
7601da177e4SLinus Torvalds }
7611da177e4SLinus Torvalds /* If we have a partial final page, deal with it now. */
7621da177e4SLinus Torvalds if (cb_max_ofs && cb_pos < cb_end) {
7631da177e4SLinus Torvalds page = pages[cur_page];
7641da177e4SLinus Torvalds if (page)
7651da177e4SLinus Torvalds memset(page_address(page) + cur_ofs, 0,
7661da177e4SLinus Torvalds cb_max_ofs - cur_ofs);
7671da177e4SLinus Torvalds /*
7681da177e4SLinus Torvalds * No need to update cb_pos at this stage:
7691da177e4SLinus Torvalds * cb_pos += cb_max_ofs - cur_ofs;
7701da177e4SLinus Torvalds */
7711da177e4SLinus Torvalds cur_ofs = cb_max_ofs;
7721da177e4SLinus Torvalds }
7731da177e4SLinus Torvalds } else if (vcn == start_vcn) {
7741da177e4SLinus Torvalds /* We can't sleep so we need two stages. */
7751da177e4SLinus Torvalds unsigned int cur2_page = cur_page;
7761da177e4SLinus Torvalds unsigned int cur_ofs2 = cur_ofs;
7771da177e4SLinus Torvalds u8 *cb_pos2 = cb_pos;
7781da177e4SLinus Torvalds
7791da177e4SLinus Torvalds ntfs_debug("Found uncompressed compression block.");
7801da177e4SLinus Torvalds /* Uncompressed cb, copy it to the destination pages. */
7811da177e4SLinus Torvalds /*
7821da177e4SLinus Torvalds * TODO: As a big optimization, we could detect this case
7832c69e205SMatthew Wilcox (Oracle) * before we read all the pages and use block_read_full_folio()
7841da177e4SLinus Torvalds * on all full pages instead (we still have to treat partial
7851da177e4SLinus Torvalds * pages especially but at least we are getting rid of the
7861da177e4SLinus Torvalds * synchronous io for the majority of pages.
7871da177e4SLinus Torvalds * Or if we choose not to do the read-ahead/-behind stuff, we
7882c69e205SMatthew Wilcox (Oracle) * could just return block_read_full_folio(pages[xpage]) as long
789ea1754a0SKirill A. Shutemov * as PAGE_SIZE <= cb_size.
7901da177e4SLinus Torvalds */
7911da177e4SLinus Torvalds if (cb_max_ofs)
7921da177e4SLinus Torvalds cb_max_page--;
7931da177e4SLinus Torvalds /* First stage: copy data into destination pages. */
7941da177e4SLinus Torvalds for (; cur_page < cb_max_page; cur_page++) {
7951da177e4SLinus Torvalds page = pages[cur_page];
7961da177e4SLinus Torvalds if (page)
7971da177e4SLinus Torvalds memcpy(page_address(page) + cur_ofs, cb_pos,
79809cbfeafSKirill A. Shutemov PAGE_SIZE - cur_ofs);
79909cbfeafSKirill A. Shutemov cb_pos += PAGE_SIZE - cur_ofs;
8001da177e4SLinus Torvalds cur_ofs = 0;
8011da177e4SLinus Torvalds if (cb_pos >= cb_end)
8021da177e4SLinus Torvalds break;
8031da177e4SLinus Torvalds }
8041da177e4SLinus Torvalds /* If we have a partial final page, deal with it now. */
8051da177e4SLinus Torvalds if (cb_max_ofs && cb_pos < cb_end) {
8061da177e4SLinus Torvalds page = pages[cur_page];
8071da177e4SLinus Torvalds if (page)
8081da177e4SLinus Torvalds memcpy(page_address(page) + cur_ofs, cb_pos,
8091da177e4SLinus Torvalds cb_max_ofs - cur_ofs);
8101da177e4SLinus Torvalds cb_pos += cb_max_ofs - cur_ofs;
8111da177e4SLinus Torvalds cur_ofs = cb_max_ofs;
8121da177e4SLinus Torvalds }
8131da177e4SLinus Torvalds /* We can sleep from now on, so drop lock. */
8141da177e4SLinus Torvalds spin_unlock(&ntfs_cb_lock);
8151da177e4SLinus Torvalds /* Second stage: finalize pages. */
8161da177e4SLinus Torvalds for (; cur2_page < cb_max_page; cur2_page++) {
8171da177e4SLinus Torvalds page = pages[cur2_page];
8181da177e4SLinus Torvalds if (page) {
8191da177e4SLinus Torvalds /*
8201da177e4SLinus Torvalds * If we are outside the initialized size, zero
8211da177e4SLinus Torvalds * the out of bounds page range.
8221da177e4SLinus Torvalds */
82336763677SAnton Altaparmakov handle_bounds_compressed_page(page, i_size,
82436763677SAnton Altaparmakov initialized_size);
8251da177e4SLinus Torvalds flush_dcache_page(page);
8261da177e4SLinus Torvalds kunmap(page);
8271da177e4SLinus Torvalds SetPageUptodate(page);
8281da177e4SLinus Torvalds unlock_page(page);
8291da177e4SLinus Torvalds if (cur2_page == xpage)
8301da177e4SLinus Torvalds xpage_done = 1;
8311da177e4SLinus Torvalds else
83209cbfeafSKirill A. Shutemov put_page(page);
8331da177e4SLinus Torvalds pages[cur2_page] = NULL;
8341da177e4SLinus Torvalds }
83509cbfeafSKirill A. Shutemov cb_pos2 += PAGE_SIZE - cur_ofs2;
8361da177e4SLinus Torvalds cur_ofs2 = 0;
8371da177e4SLinus Torvalds if (cb_pos2 >= cb_end)
8381da177e4SLinus Torvalds break;
8391da177e4SLinus Torvalds }
8401da177e4SLinus Torvalds } else {
8411da177e4SLinus Torvalds /* Compressed cb, decompress it into the destination page(s). */
8421da177e4SLinus Torvalds unsigned int prev_cur_page = cur_page;
8431da177e4SLinus Torvalds
8441da177e4SLinus Torvalds ntfs_debug("Found compressed compression block.");
8452c27ce91SKees Cook err = ntfs_decompress(pages, completed_pages, &cur_page,
8462c27ce91SKees Cook &cur_ofs, cb_max_page, cb_max_ofs, xpage,
8472c27ce91SKees Cook &xpage_done, cb_pos, cb_size - (cb_pos - cb),
8482c27ce91SKees Cook i_size, initialized_size);
8491da177e4SLinus Torvalds /*
8501da177e4SLinus Torvalds * We can sleep from now on, lock already dropped by
8511da177e4SLinus Torvalds * ntfs_decompress().
8521da177e4SLinus Torvalds */
8531da177e4SLinus Torvalds if (err) {
8541da177e4SLinus Torvalds ntfs_error(vol->sb, "ntfs_decompress() failed in inode "
8551da177e4SLinus Torvalds "0x%lx with error code %i. Skipping "
8561da177e4SLinus Torvalds "this compression block.",
8571da177e4SLinus Torvalds ni->mft_no, -err);
8581da177e4SLinus Torvalds /* Release the unfinished pages. */
8591da177e4SLinus Torvalds for (; prev_cur_page < cur_page; prev_cur_page++) {
8601da177e4SLinus Torvalds page = pages[prev_cur_page];
8611da177e4SLinus Torvalds if (page) {
8621da177e4SLinus Torvalds flush_dcache_page(page);
8631da177e4SLinus Torvalds kunmap(page);
8641da177e4SLinus Torvalds unlock_page(page);
8651da177e4SLinus Torvalds if (prev_cur_page != xpage)
86609cbfeafSKirill A. Shutemov put_page(page);
8671da177e4SLinus Torvalds pages[prev_cur_page] = NULL;
8681da177e4SLinus Torvalds }
8691da177e4SLinus Torvalds }
8701da177e4SLinus Torvalds }
8711da177e4SLinus Torvalds }
8721da177e4SLinus Torvalds
8731da177e4SLinus Torvalds /* Release the buffer heads. */
8741da177e4SLinus Torvalds for (i = 0; i < nr_bhs; i++)
8751da177e4SLinus Torvalds brelse(bhs[i]);
8761da177e4SLinus Torvalds
8771da177e4SLinus Torvalds /* Do we have more work to do? */
8781da177e4SLinus Torvalds if (nr_cbs)
8791da177e4SLinus Torvalds goto do_next_cb;
8801da177e4SLinus Torvalds
8811da177e4SLinus Torvalds /* We no longer need the list of buffer heads. */
8821da177e4SLinus Torvalds kfree(bhs);
8831da177e4SLinus Torvalds
8841da177e4SLinus Torvalds /* Clean up if we have any pages left. Should never happen. */
8851da177e4SLinus Torvalds for (cur_page = 0; cur_page < max_page; cur_page++) {
8861da177e4SLinus Torvalds page = pages[cur_page];
8871da177e4SLinus Torvalds if (page) {
8881da177e4SLinus Torvalds ntfs_error(vol->sb, "Still have pages left! "
8891da177e4SLinus Torvalds "Terminating them with extreme "
8901da177e4SLinus Torvalds "prejudice. Inode 0x%lx, page index "
8911da177e4SLinus Torvalds "0x%lx.", ni->mft_no, page->index);
8921da177e4SLinus Torvalds flush_dcache_page(page);
8931da177e4SLinus Torvalds kunmap(page);
8941da177e4SLinus Torvalds unlock_page(page);
8951da177e4SLinus Torvalds if (cur_page != xpage)
89609cbfeafSKirill A. Shutemov put_page(page);
8971da177e4SLinus Torvalds pages[cur_page] = NULL;
8981da177e4SLinus Torvalds }
8991da177e4SLinus Torvalds }
9001da177e4SLinus Torvalds
9011da177e4SLinus Torvalds /* We no longer need the list of pages. */
9021da177e4SLinus Torvalds kfree(pages);
9032c27ce91SKees Cook kfree(completed_pages);
9041da177e4SLinus Torvalds
9051da177e4SLinus Torvalds /* If we have completed the requested page, we return success. */
9061da177e4SLinus Torvalds if (likely(xpage_done))
9071da177e4SLinus Torvalds return 0;
9081da177e4SLinus Torvalds
9091da177e4SLinus Torvalds ntfs_debug("Failed. Returning error code %s.", err == -EOVERFLOW ?
910af901ca1SAndré Goddard Rosa "EOVERFLOW" : (!err ? "EIO" : "unknown error"));
9111da177e4SLinus Torvalds return err < 0 ? err : -EIO;
9121da177e4SLinus Torvalds
9131da177e4SLinus Torvalds read_err:
9141da177e4SLinus Torvalds ntfs_error(vol->sb, "IO error while reading compressed data.");
9151da177e4SLinus Torvalds /* Release the buffer heads. */
9161da177e4SLinus Torvalds for (i = 0; i < nr_bhs; i++)
9171da177e4SLinus Torvalds brelse(bhs[i]);
9181da177e4SLinus Torvalds goto err_out;
9191da177e4SLinus Torvalds
9201da177e4SLinus Torvalds map_rl_err:
9211da177e4SLinus Torvalds ntfs_error(vol->sb, "ntfs_map_runlist() failed. Cannot read "
9221da177e4SLinus Torvalds "compression block.");
9231da177e4SLinus Torvalds goto err_out;
9241da177e4SLinus Torvalds
9251da177e4SLinus Torvalds rl_err:
9261da177e4SLinus Torvalds up_read(&ni->runlist.lock);
9271da177e4SLinus Torvalds ntfs_error(vol->sb, "ntfs_rl_vcn_to_lcn() failed. Cannot read "
9281da177e4SLinus Torvalds "compression block.");
9291da177e4SLinus Torvalds goto err_out;
9301da177e4SLinus Torvalds
9311da177e4SLinus Torvalds getblk_err:
9321da177e4SLinus Torvalds up_read(&ni->runlist.lock);
9331da177e4SLinus Torvalds ntfs_error(vol->sb, "getblk() failed. Cannot read compression block.");
9341da177e4SLinus Torvalds
9351da177e4SLinus Torvalds err_out:
9361da177e4SLinus Torvalds kfree(bhs);
9371da177e4SLinus Torvalds for (i = cur_page; i < max_page; i++) {
9381da177e4SLinus Torvalds page = pages[i];
9391da177e4SLinus Torvalds if (page) {
9401da177e4SLinus Torvalds flush_dcache_page(page);
9411da177e4SLinus Torvalds kunmap(page);
9421da177e4SLinus Torvalds unlock_page(page);
9431da177e4SLinus Torvalds if (i != xpage)
94409cbfeafSKirill A. Shutemov put_page(page);
9451da177e4SLinus Torvalds }
9461da177e4SLinus Torvalds }
9471da177e4SLinus Torvalds kfree(pages);
9482c27ce91SKees Cook kfree(completed_pages);
9491da177e4SLinus Torvalds return -EIO;
9501da177e4SLinus Torvalds }
951