1/** 2 * compress.c - Compressed attribute handling code. Originated from the Linux-NTFS 3 * project. 4 * 5 * Copyright (c) 2004-2005 Anton Altaparmakov 6 * Copyright (c) 2004-2006 Szabolcs Szakacsits 7 * Copyright (c) 2005 Yura Pakhuchiy 8 * Copyright (c) 2009-2011 Jean-Pierre Andre 9 * 10 * This program/include file is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU General Public License as published 12 * by the Free Software Foundation; either version 2 of the License, or 13 * (at your option) any later version. 14 * 15 * This program/include file is distributed in the hope that it will be 16 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 17 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program (in the main directory of the NTFS-3G 22 * distribution in the file COPYING); if not, write to the Free Software 23 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 24 * 25 * A part of the compression algorithm is based on lzhuf.c whose header 26 * describes the roles of the original authors (with no apparent copyright 27 * notice, and according to http://home.earthlink.net/~neilbawd/pall.html 28 * this was put into public domain in 1988 by Haruhiko OKUMURA). 29 * 30 * LZHUF.C English version 1.0 31 * Based on Japanese version 29-NOV-1988 32 * LZSS coded by Haruhiko OKUMURA 33 * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI 34 * Edited and translated to English by Kenji RIKITAKE 35 */ 36 37#ifdef HAVE_CONFIG_H 38#include "config.h" 39#endif 40 41#ifdef HAVE_STDIO_H 42#include <stdio.h> 43#endif 44#ifdef HAVE_STRING_H 45#include <string.h> 46#endif 47#ifdef HAVE_STDLIB_H 48#include <stdlib.h> 49#endif 50#ifdef HAVE_ERRNO_H 51#include <errno.h> 52#endif 53 54#include "attrib.h" 55#include "debug.h" 56#include "volume.h" 57#include "types.h" 58#include "layout.h" 59#include "runlist.h" 60#include "compress.h" 61#include "lcnalloc.h" 62#include "logging.h" 63#include "misc.h" 64 65#undef le16_to_cpup 66/* the standard le16_to_cpup() crashes for unaligned data on some processors */ 67#define le16_to_cpup(p) (*(u8*)(p) + (((u8*)(p))[1] << 8)) 68 69/** 70 * enum ntfs_compression_constants - constants used in the compression code 71 */ 72typedef enum { 73 /* Token types and access mask. */ 74 NTFS_SYMBOL_TOKEN = 0, 75 NTFS_PHRASE_TOKEN = 1, 76 NTFS_TOKEN_MASK = 1, 77 78 /* Compression sub-block constants. */ 79 NTFS_SB_SIZE_MASK = 0x0fff, 80 NTFS_SB_SIZE = 0x1000, 81 NTFS_SB_IS_COMPRESSED = 0x8000, 82} ntfs_compression_constants; 83 84struct COMPRESS_CONTEXT { 85 const unsigned char *inbuf; 86 int bufsize; 87 int size; 88 int rel; 89 int mxsz; 90 s16 head[256]; 91 s16 lson[NTFS_SB_SIZE]; 92 s16 rson[NTFS_SB_SIZE]; 93} ; 94 95/* 96 * Search for the longest sequence matching current position 97 * 98 * A binary tree is maintained to locate all previously met sequences, 99 * and this function has to be called for all of them. 100 * 101 * This function is heavily used, it has to be optimized carefully 102 * 103 * Returns the size of the longest match, 104 * zero if no match is found. 105 */ 106 107static int ntfs_best_match(struct COMPRESS_CONTEXT *pctx, int i) 108{ 109 s16 *prev; 110 int node; 111 register long j; 112 long maxpos; 113 long startj; 114 long bestj; 115 int bufsize; 116 int bestnode; 117 register const unsigned char *p1,*p2; 118 119 p1 = pctx->inbuf; 120 node = pctx->head[p1[i] & 255]; 121 if (node >= 0) { 122 /* search the best match at current position */ 123 bestnode = node; 124 bufsize = pctx->bufsize; 125 /* restrict matches to the longest allowed sequence */ 126 maxpos = bufsize; 127 if ((i + pctx->mxsz) < maxpos) 128 maxpos = i + pctx->mxsz; 129 startj = i + 1 - maxpos; 130 bestj = startj; 131 /* make indexes relative to end of allowed position */ 132 p1 = &p1[maxpos]; 133 if (startj < 0) { 134 do { 135 /* indexes are negative */ 136 p2 = &p1[node - i]; 137 /* no need to compare the first byte */ 138 j = startj; 139 /* the second byte cannot lead to useful compression */ 140 if (p1[j] == p2[j]) { 141 j++; 142 if (j < 0) { 143 do { 144 } while ((p1[j] == p2[j]) 145 && (++j < 0)); 146 } 147 /* remember the match, if better */ 148 if (j > bestj) { 149 bestj = j; 150 bestnode = node; 151 } 152 } 153 /* walk in the tree in the right direction */ 154 if ((j < 0) && (p1[j] < p2[j])) 155 prev = &pctx->lson[node]; 156 else 157 prev = &pctx->rson[node]; 158 node = *prev; 159 /* stop if reaching a leaf or maximum length */ 160 } while ((node >= 0) && (j < 0)); 161 /* put the node into the tree if we reached a leaf */ 162 if (node < 0) 163 *prev = i; 164 } 165 /* done, return the best match */ 166 pctx->size = bestj + maxpos - i; 167 pctx->rel = bestnode - i; 168 } else { 169 pctx->head[p1[i] & 255] = i; 170 pctx->size = 0; 171 pctx->rel = 0; 172 } 173 return (pctx->size); 174} 175 176/* 177 * Compress a 4096-byte block 178 * 179 * Returns a header of two bytes followed by the compressed data. 180 * If compression is not effective, the header and an uncompressed 181 * block is returned. 182 * 183 * Note : two bytes may be output before output buffer overflow 184 * is detected, so a 4100-bytes output buffer must be reserved. 185 * 186 * Returns the size of the compressed block, including the 187 * header (minimal size is 2, maximum size is 4098) 188 * 0 if an error has been met. 189 */ 190 191static unsigned int ntfs_compress_block(const char *inbuf, int bufsize, 192 char *outbuf) 193{ 194 struct COMPRESS_CONTEXT *pctx; 195 int i; /* current position */ 196 int j; /* end of best match from current position */ 197 int k; /* end of best match from next position */ 198 int offs; /* offset to best match */ 199 int n; 200 int bp; /* bits to store offset */ 201 int mxoff; /* max match offset : 1 << bp */ 202 int mxsz2; 203 unsigned int xout; 204 unsigned int q; /* aggregated offset and size */ 205 int done; 206 char *ptag; /* location reserved for a tag */ 207 int tag; /* current value of tag */ 208 int ntag; /* count of bits still undefined in tag */ 209 210 pctx = (struct COMPRESS_CONTEXT*)ntfs_malloc(sizeof(struct COMPRESS_CONTEXT)); 211 if (pctx) { 212 for (n=0; n<NTFS_SB_SIZE; n++) 213 pctx->lson[n] = pctx->rson[n] = -1; 214 for (n=0; n<256; n++) 215 pctx->head[n] = -1; 216 pctx->inbuf = (const unsigned char*)inbuf; 217 pctx->bufsize = bufsize; 218 xout = 2; 219 n = 0; 220 i = 0; 221 bp = 4; 222 mxoff = 1 << bp; 223 pctx->mxsz = (1 << (16 - bp)) + 2; 224 tag = 0; 225 done = -1; 226 ntag = 8; 227 ptag = &outbuf[xout++]; 228 while ((i < bufsize) && (xout < (NTFS_SB_SIZE + 2))) { 229 /* adjust the longest match we can output */ 230 while (mxoff < i) { 231 bp++; 232 mxoff <<= 1; 233 pctx->mxsz = (pctx->mxsz + 2) >> 1; 234 } 235 /* search the best match at current position */ 236 if (done < i) 237 do { 238 ntfs_best_match(pctx,++done); 239 } while (done < i); 240 j = i + pctx->size; 241 if ((j - i) > pctx->mxsz) 242 j = i + pctx->mxsz; 243 244 if ((j - i) > 2) { 245 offs = pctx->rel; 246 /* check whether there is a better run at i+1 */ 247 ntfs_best_match(pctx,i+1); 248 done = i+1; 249 k = i + 1 + pctx->size; 250 mxsz2 = pctx->mxsz; 251 if (mxoff <= i) 252 mxsz2 = (pctx->mxsz + 2) >> 1; 253 if ((k - i) > mxsz2) 254 k = i + mxsz2; 255 if (k > (j + 1)) { 256 /* issue a single byte */ 257 outbuf[xout++] = inbuf[i]; 258 i++; 259 } else { 260 q = (~offs << (16 - bp)) 261 + (j - i - 3); 262 outbuf[xout++] = q & 255; 263 outbuf[xout++] = (q >> 8) & 255; 264 tag |= (1 << (8 - ntag)); 265 i = j; 266 } 267 } else { 268 outbuf[xout++] = inbuf[i]; 269 i++; 270 } 271 /* store the tag if fully used */ 272 if (!--ntag) { 273 *ptag = tag; 274 ntag = 8; 275 ptag = &outbuf[xout++]; 276 tag = 0; 277 } 278 } 279 /* store the last tag, if partially used */ 280 if (ntag == 8) 281 xout--; 282 else 283 *ptag = tag; 284 /* uncompressed must be full size, accept if better */ 285 if ((i >= bufsize) && (xout < (NTFS_SB_SIZE + 2))) { 286 outbuf[0] = (xout - 3) & 255; 287 outbuf[1] = 0xb0 + (((xout - 3) >> 8) & 15); 288 } else { 289 memcpy(&outbuf[2],inbuf,bufsize); 290 if (bufsize < NTFS_SB_SIZE) 291 memset(&outbuf[bufsize+2], 0, 292 NTFS_SB_SIZE - bufsize); 293 outbuf[0] = 0xff; 294 outbuf[1] = 0x3f; 295 xout = NTFS_SB_SIZE + 2; 296 } 297 free(pctx); 298 } else { 299 xout = 0; 300 errno = ENOMEM; 301 } 302 return (xout); 303} 304 305/** 306 * ntfs_decompress - decompress a compression block into an array of pages 307 * @dest: buffer to which to write the decompressed data 308 * @dest_size: size of buffer @dest in bytes 309 * @cb_start: compression block to decompress 310 * @cb_size: size of compression block @cb_start in bytes 311 * 312 * This decompresses the compression block @cb_start into the destination 313 * buffer @dest. 314 * 315 * @cb_start is a pointer to the compression block which needs decompressing 316 * and @cb_size is the size of @cb_start in bytes (8-64kiB). 317 * 318 * Return 0 if success or -EOVERFLOW on error in the compressed stream. 319 */ 320static int ntfs_decompress(u8 *dest, const u32 dest_size, 321 u8 *const cb_start, const u32 cb_size) 322{ 323 /* 324 * Pointers into the compressed data, i.e. the compression block (cb), 325 * and the therein contained sub-blocks (sb). 326 */ 327 u8 *cb_end = cb_start + cb_size; /* End of cb. */ 328 u8 *cb = cb_start; /* Current position in cb. */ 329 u8 *cb_sb_start = cb; /* Beginning of the current sb in the cb. */ 330 u8 *cb_sb_end; /* End of current sb / beginning of next sb. */ 331 /* Variables for uncompressed data / destination. */ 332 u8 *dest_end = dest + dest_size; /* End of dest buffer. */ 333 u8 *dest_sb_start; /* Start of current sub-block in dest. */ 334 u8 *dest_sb_end; /* End of current sb in dest. */ 335 /* Variables for tag and token parsing. */ 336 u8 tag; /* Current tag. */ 337 int token; /* Loop counter for the eight tokens in tag. */ 338 339 ntfs_log_trace("Entering, cb_size = 0x%x.\n", (unsigned)cb_size); 340do_next_sb: 341 ntfs_log_debug("Beginning sub-block at offset = %d in the cb.\n", 342 (int)(cb - cb_start)); 343 /* 344 * Have we reached the end of the compression block or the end of the 345 * decompressed data? The latter can happen for example if the current 346 * position in the compression block is one byte before its end so the 347 * first two checks do not detect it. 348 */ 349 if (cb == cb_end || !le16_to_cpup((le16*)cb) || dest == dest_end) { 350 ntfs_log_debug("Completed. Returning success (0).\n"); 351 return 0; 352 } 353 /* Setup offset for the current sub-block destination. */ 354 dest_sb_start = dest; 355 dest_sb_end = dest + NTFS_SB_SIZE; 356 /* Check that we are still within allowed boundaries. */ 357 if (dest_sb_end > dest_end) 358 goto return_overflow; 359 /* Does the minimum size of a compressed sb overflow valid range? */ 360 if (cb + 6 > cb_end) 361 goto return_overflow; 362 /* Setup the current sub-block source pointers and validate range. */ 363 cb_sb_start = cb; 364 cb_sb_end = cb_sb_start + (le16_to_cpup((le16*)cb) & NTFS_SB_SIZE_MASK) 365 + 3; 366 if (cb_sb_end > cb_end) 367 goto return_overflow; 368 /* Now, we are ready to process the current sub-block (sb). */ 369 if (!(le16_to_cpup((le16*)cb) & NTFS_SB_IS_COMPRESSED)) { 370 ntfs_log_debug("Found uncompressed sub-block.\n"); 371 /* This sb is not compressed, just copy it into destination. */ 372 /* Advance source position to first data byte. */ 373 cb += 2; 374 /* An uncompressed sb must be full size. */ 375 if (cb_sb_end - cb != NTFS_SB_SIZE) 376 goto return_overflow; 377 /* Copy the block and advance the source position. */ 378 memcpy(dest, cb, NTFS_SB_SIZE); 379 cb += NTFS_SB_SIZE; 380 /* Advance destination position to next sub-block. */ 381 dest += NTFS_SB_SIZE; 382 goto do_next_sb; 383 } 384 ntfs_log_debug("Found compressed sub-block.\n"); 385 /* This sb is compressed, decompress it into destination. */ 386 /* Forward to the first tag in the sub-block. */ 387 cb += 2; 388do_next_tag: 389 if (cb == cb_sb_end) { 390 /* Check if the decompressed sub-block was not full-length. */ 391 if (dest < dest_sb_end) { 392 int nr_bytes = dest_sb_end - dest; 393 394 ntfs_log_debug("Filling incomplete sub-block with zeroes.\n"); 395 /* Zero remainder and update destination position. */ 396 memset(dest, 0, nr_bytes); 397 dest += nr_bytes; 398 } 399 /* We have finished the current sub-block. */ 400 goto do_next_sb; 401 } 402 /* Check we are still in range. */ 403 if (cb > cb_sb_end || dest > dest_sb_end) 404 goto return_overflow; 405 /* Get the next tag and advance to first token. */ 406 tag = *cb++; 407 /* Parse the eight tokens described by the tag. */ 408 for (token = 0; token < 8; token++, tag >>= 1) { 409 u16 lg, pt, length, max_non_overlap; 410 register u16 i; 411 u8 *dest_back_addr; 412 413 /* Check if we are done / still in range. */ 414 if (cb >= cb_sb_end || dest > dest_sb_end) 415 break; 416 /* Determine token type and parse appropriately.*/ 417 if ((tag & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) { 418 /* 419 * We have a symbol token, copy the symbol across, and 420 * advance the source and destination positions. 421 */ 422 *dest++ = *cb++; 423 /* Continue with the next token. */ 424 continue; 425 } 426 /* 427 * We have a phrase token. Make sure it is not the first tag in 428 * the sb as this is illegal and would confuse the code below. 429 */ 430 if (dest == dest_sb_start) 431 goto return_overflow; 432 /* 433 * Determine the number of bytes to go back (p) and the number 434 * of bytes to copy (l). We use an optimized algorithm in which 435 * we first calculate log2(current destination position in sb), 436 * which allows determination of l and p in O(1) rather than 437 * O(n). We just need an arch-optimized log2() function now. 438 */ 439 lg = 0; 440 for (i = dest - dest_sb_start - 1; i >= 0x10; i >>= 1) 441 lg++; 442 /* Get the phrase token into i. */ 443 pt = le16_to_cpup((le16*)cb); 444 /* 445 * Calculate starting position of the byte sequence in 446 * the destination using the fact that p = (pt >> (12 - lg)) + 1 447 * and make sure we don't go too far back. 448 */ 449 dest_back_addr = dest - (pt >> (12 - lg)) - 1; 450 if (dest_back_addr < dest_sb_start) 451 goto return_overflow; 452 /* Now calculate the length of the byte sequence. */ 453 length = (pt & (0xfff >> lg)) + 3; 454 /* Verify destination is in range. */ 455 if (dest + length > dest_sb_end) 456 goto return_overflow; 457 /* The number of non-overlapping bytes. */ 458 max_non_overlap = dest - dest_back_addr; 459 if (length <= max_non_overlap) { 460 /* The byte sequence doesn't overlap, just copy it. */ 461 memcpy(dest, dest_back_addr, length); 462 /* Advance destination pointer. */ 463 dest += length; 464 } else { 465 /* 466 * The byte sequence does overlap, copy non-overlapping 467 * part and then do a slow byte by byte copy for the 468 * overlapping part. Also, advance the destination 469 * pointer. 470 */ 471 memcpy(dest, dest_back_addr, max_non_overlap); 472 dest += max_non_overlap; 473 dest_back_addr += max_non_overlap; 474 length -= max_non_overlap; 475 while (length--) 476 *dest++ = *dest_back_addr++; 477 } 478 /* Advance source position and continue with the next token. */ 479 cb += 2; 480 } 481 /* No tokens left in the current tag. Continue with the next tag. */ 482 goto do_next_tag; 483return_overflow: 484 errno = EOVERFLOW; 485 ntfs_log_perror("Failed to decompress file"); 486 return -1; 487} 488 489/** 490 * ntfs_is_cb_compressed - internal function, do not use 491 * 492 * This is a very specialised function determining if a cb is compressed or 493 * uncompressed. It is assumed that checking for a sparse cb has already been 494 * performed and that the cb is not sparse. It makes all sorts of other 495 * assumptions as well and hence it is not useful anywhere other than where it 496 * is used at the moment. Please, do not make this function available for use 497 * outside of compress.c as it is bound to confuse people and not do what they 498 * want. 499 * 500 * Return TRUE on errors so that the error will be detected later on in the 501 * code. Might be a bit confusing to debug but there really should never be 502 * errors coming from here. 503 */ 504static BOOL ntfs_is_cb_compressed(ntfs_attr *na, runlist_element *rl, 505 VCN cb_start_vcn, int cb_clusters) 506{ 507 /* 508 * The simplest case: the run starting at @cb_start_vcn contains 509 * @cb_clusters clusters which are all not sparse, thus the cb is not 510 * compressed. 511 */ 512restart: 513 cb_clusters -= rl->length - (cb_start_vcn - rl->vcn); 514 while (cb_clusters > 0) { 515 /* Go to the next run. */ 516 rl++; 517 /* Map the next runlist fragment if it is not mapped. */ 518 if (rl->lcn < LCN_HOLE || !rl->length) { 519 cb_start_vcn = rl->vcn; 520 rl = ntfs_attr_find_vcn(na, rl->vcn); 521 if (!rl || rl->lcn < LCN_HOLE || !rl->length) 522 return TRUE; 523 /* 524 * If the runs were merged need to deal with the 525 * resulting partial run so simply restart. 526 */ 527 if (rl->vcn < cb_start_vcn) 528 goto restart; 529 } 530 /* If the current run is sparse, the cb is compressed. */ 531 if (rl->lcn == LCN_HOLE) 532 return TRUE; 533 /* If the whole cb is not sparse, it is not compressed. */ 534 if (rl->length >= cb_clusters) 535 return FALSE; 536 cb_clusters -= rl->length; 537 }; 538 /* All cb_clusters were not sparse thus the cb is not compressed. */ 539 return FALSE; 540} 541 542/** 543 * ntfs_compressed_attr_pread - read from a compressed attribute 544 * @na: ntfs attribute to read from 545 * @pos: byte position in the attribute to begin reading from 546 * @count: number of bytes to read 547 * @b: output data buffer 548 * 549 * NOTE: You probably want to be using attrib.c::ntfs_attr_pread() instead. 550 * 551 * This function will read @count bytes starting at offset @pos from the 552 * compressed ntfs attribute @na into the data buffer @b. 553 * 554 * On success, return the number of successfully read bytes. If this number 555 * is lower than @count this means that the read reached end of file or that 556 * an error was encountered during the read so that the read is partial. 557 * 0 means end of file or nothing was read (also return 0 when @count is 0). 558 * 559 * On error and nothing has been read, return -1 with errno set appropriately 560 * to the return code of ntfs_pread(), or to EINVAL in case of invalid 561 * arguments. 562 */ 563s64 ntfs_compressed_attr_pread(ntfs_attr *na, s64 pos, s64 count, void *b) 564{ 565 s64 br, to_read, ofs, total, total2; 566 u64 cb_size_mask; 567 VCN start_vcn, vcn, end_vcn; 568 ntfs_volume *vol; 569 runlist_element *rl; 570 u8 *dest, *cb, *cb_pos, *cb_end; 571 u32 cb_size; 572 int err; 573 ATTR_FLAGS data_flags; 574 FILE_ATTR_FLAGS compression; 575 unsigned int nr_cbs, cb_clusters; 576 577 ntfs_log_trace("Entering for inode 0x%llx, attr 0x%x, pos 0x%llx, count 0x%llx.\n", 578 (unsigned long long)na->ni->mft_no, na->type, 579 (long long)pos, (long long)count); 580 data_flags = na->data_flags; 581 compression = na->ni->flags & FILE_ATTR_COMPRESSED; 582 if (!na || !na->ni || !na->ni->vol || !b 583 || ((data_flags & ATTR_COMPRESSION_MASK) 584 != ATTR_IS_COMPRESSED) 585 || pos < 0 || count < 0) { 586 errno = EINVAL; 587 return -1; 588 } 589 /* 590 * Encrypted attributes are not supported. We return access denied, 591 * which is what Windows NT4 does, too. 592 */ 593 if (NAttrEncrypted(na)) { 594 errno = EACCES; 595 return -1; 596 } 597 if (!count) 598 return 0; 599 /* Truncate reads beyond end of attribute. */ 600 if (pos + count > na->data_size) { 601 if (pos >= na->data_size) { 602 return 0; 603 } 604 count = na->data_size - pos; 605 } 606 /* If it is a resident attribute, simply use ntfs_attr_pread(). */ 607 if (!NAttrNonResident(na)) 608 return ntfs_attr_pread(na, pos, count, b); 609 total = total2 = 0; 610 /* Zero out reads beyond initialized size. */ 611 if (pos + count > na->initialized_size) { 612 if (pos >= na->initialized_size) { 613 memset(b, 0, count); 614 return count; 615 } 616 total2 = pos + count - na->initialized_size; 617 count -= total2; 618 memset((u8*)b + count, 0, total2); 619 } 620 vol = na->ni->vol; 621 cb_size = na->compression_block_size; 622 cb_size_mask = cb_size - 1UL; 623 cb_clusters = na->compression_block_clusters; 624 625 /* Need a temporary buffer for each loaded compression block. */ 626 cb = (u8*)ntfs_malloc(cb_size); 627 if (!cb) 628 return -1; 629 630 /* Need a temporary buffer for each uncompressed block. */ 631 dest = (u8*)ntfs_malloc(cb_size); 632 if (!dest) { 633 free(cb); 634 return -1; 635 } 636 /* 637 * The first vcn in the first compression block (cb) which we need to 638 * decompress. 639 */ 640 start_vcn = (pos & ~cb_size_mask) >> vol->cluster_size_bits; 641 /* Offset in the uncompressed cb at which to start reading data. */ 642 ofs = pos & cb_size_mask; 643 /* 644 * The first vcn in the cb after the last cb which we need to 645 * decompress. 646 */ 647 end_vcn = ((pos + count + cb_size - 1) & ~cb_size_mask) >> 648 vol->cluster_size_bits; 649 /* Number of compression blocks (cbs) in the wanted vcn range. */ 650 nr_cbs = (end_vcn - start_vcn) << vol->cluster_size_bits >> 651 na->compression_block_size_bits; 652 cb_end = cb + cb_size; 653do_next_cb: 654 nr_cbs--; 655 cb_pos = cb; 656 vcn = start_vcn; 657 start_vcn += cb_clusters; 658 659 /* Check whether the compression block is sparse. */ 660 rl = ntfs_attr_find_vcn(na, vcn); 661 if (!rl || rl->lcn < LCN_HOLE) { 662 free(cb); 663 free(dest); 664 if (total) 665 return total; 666 /* FIXME: Do we want EIO or the error code? (AIA) */ 667 errno = EIO; 668 return -1; 669 } 670 if (rl->lcn == LCN_HOLE) { 671 /* Sparse cb, zero out destination range overlapping the cb. */ 672 ntfs_log_debug("Found sparse compression block.\n"); 673 to_read = min(count, cb_size - ofs); 674 memset(b, 0, to_read); 675 ofs = 0; 676 total += to_read; 677 count -= to_read; 678 b = (u8*)b + to_read; 679 } else if (!ntfs_is_cb_compressed(na, rl, vcn, cb_clusters)) { 680 s64 tdata_size, tinitialized_size; 681 /* 682 * Uncompressed cb, read it straight into the destination range 683 * overlapping the cb. 684 */ 685 ntfs_log_debug("Found uncompressed compression block.\n"); 686 /* 687 * Read the uncompressed data into the destination buffer. 688 * NOTE: We cheat a little bit here by marking the attribute as 689 * not compressed in the ntfs_attr structure so that we can 690 * read the data by simply using ntfs_attr_pread(). (-8 691 * NOTE: we have to modify data_size and initialized_size 692 * temporarily as well... 693 */ 694 to_read = min(count, cb_size - ofs); 695 ofs += vcn << vol->cluster_size_bits; 696 NAttrClearCompressed(na); 697 na->data_flags &= ~ATTR_COMPRESSION_MASK; 698 tdata_size = na->data_size; 699 tinitialized_size = na->initialized_size; 700 na->data_size = na->initialized_size = na->allocated_size; 701 do { 702 br = ntfs_attr_pread(na, ofs, to_read, b); 703 if (br <= 0) { 704 if (!br) { 705 ntfs_log_error("Failed to read an" 706 " uncompressed cluster," 707 " inode %lld offs 0x%llx\n", 708 (long long)na->ni->mft_no, 709 (long long)ofs); 710 errno = EIO; 711 } 712 err = errno; 713 na->data_size = tdata_size; 714 na->initialized_size = tinitialized_size; 715 na->ni->flags |= compression; 716 na->data_flags = data_flags; 717 free(cb); 718 free(dest); 719 if (total) 720 return total; 721 errno = err; 722 return br; 723 } 724 total += br; 725 count -= br; 726 b = (u8*)b + br; 727 to_read -= br; 728 ofs += br; 729 } while (to_read > 0); 730 na->data_size = tdata_size; 731 na->initialized_size = tinitialized_size; 732 na->ni->flags |= compression; 733 na->data_flags = data_flags; 734 ofs = 0; 735 } else { 736 s64 tdata_size, tinitialized_size; 737 738 /* 739 * Compressed cb, decompress it into the temporary buffer, then 740 * copy the data to the destination range overlapping the cb. 741 */ 742 ntfs_log_debug("Found compressed compression block.\n"); 743 /* 744 * Read the compressed data into the temporary buffer. 745 * NOTE: We cheat a little bit here by marking the attribute as 746 * not compressed in the ntfs_attr structure so that we can 747 * read the raw, compressed data by simply using 748 * ntfs_attr_pread(). (-8 749 * NOTE: We have to modify data_size and initialized_size 750 * temporarily as well... 751 */ 752 to_read = cb_size; 753 NAttrClearCompressed(na); 754 na->data_flags &= ~ATTR_COMPRESSION_MASK; 755 tdata_size = na->data_size; 756 tinitialized_size = na->initialized_size; 757 na->data_size = na->initialized_size = na->allocated_size; 758 do { 759 br = ntfs_attr_pread(na, 760 (vcn << vol->cluster_size_bits) + 761 (cb_pos - cb), to_read, cb_pos); 762 if (br <= 0) { 763 if (!br) { 764 ntfs_log_error("Failed to read a" 765 " compressed cluster, " 766 " inode %lld offs 0x%llx\n", 767 (long long)na->ni->mft_no, 768 (long long)(vcn << vol->cluster_size_bits)); 769 errno = EIO; 770 } 771 err = errno; 772 na->data_size = tdata_size; 773 na->initialized_size = tinitialized_size; 774 na->ni->flags |= compression; 775 na->data_flags = data_flags; 776 free(cb); 777 free(dest); 778 if (total) 779 return total; 780 errno = err; 781 return br; 782 } 783 cb_pos += br; 784 to_read -= br; 785 } while (to_read > 0); 786 na->data_size = tdata_size; 787 na->initialized_size = tinitialized_size; 788 na->ni->flags |= compression; 789 na->data_flags = data_flags; 790 /* Just a precaution. */ 791 if (cb_pos + 2 <= cb_end) 792 *(u16*)cb_pos = 0; 793 ntfs_log_debug("Successfully read the compression block.\n"); 794 if (ntfs_decompress(dest, cb_size, cb, cb_size) < 0) { 795 err = errno; 796 free(cb); 797 free(dest); 798 if (total) 799 return total; 800 errno = err; 801 return -1; 802 } 803 to_read = min(count, cb_size - ofs); 804 memcpy(b, dest + ofs, to_read); 805 total += to_read; 806 count -= to_read; 807 b = (u8*)b + to_read; 808 ofs = 0; 809 } 810 /* Do we have more work to do? */ 811 if (nr_cbs) 812 goto do_next_cb; 813 /* We no longer need the buffers. */ 814 free(cb); 815 free(dest); 816 /* Return number of bytes read. */ 817 return total + total2; 818} 819 820/* 821 * Read data from a set of clusters 822 * 823 * Returns the amount of data read 824 */ 825 826static u32 read_clusters(ntfs_volume *vol, const runlist_element *rl, 827 s64 offs, u32 to_read, char *inbuf) 828{ 829 u32 count; 830 int xgot; 831 u32 got; 832 s64 xpos; 833 BOOL first; 834 char *xinbuf; 835 const runlist_element *xrl; 836 837 got = 0; 838 xrl = rl; 839 xinbuf = inbuf; 840 first = TRUE; 841 do { 842 count = xrl->length << vol->cluster_size_bits; 843 xpos = xrl->lcn << vol->cluster_size_bits; 844 if (first) { 845 count -= offs; 846 xpos += offs; 847 } 848 if ((to_read - got) < count) 849 count = to_read - got; 850 xgot = ntfs_pread(vol->dev, xpos, count, xinbuf); 851 if (xgot == (int)count) { 852 got += count; 853 xpos += count; 854 xinbuf += count; 855 xrl++; 856 } 857 first = FALSE; 858 } while ((xgot == (int)count) && (got < to_read)); 859 return (got); 860} 861 862/* 863 * Write data to a set of clusters 864 * 865 * Returns the amount of data written 866 */ 867 868static s32 write_clusters(ntfs_volume *vol, const runlist_element *rl, 869 s64 offs, s32 to_write, const char *outbuf) 870{ 871 s32 count; 872 s32 put, xput; 873 s64 xpos; 874 BOOL first; 875 const char *xoutbuf; 876 const runlist_element *xrl; 877 878 put = 0; 879 xrl = rl; 880 xoutbuf = outbuf; 881 first = TRUE; 882 do { 883 count = xrl->length << vol->cluster_size_bits; 884 xpos = xrl->lcn << vol->cluster_size_bits; 885 if (first) { 886 count -= offs; 887 xpos += offs; 888 } 889 if ((to_write - put) < count) 890 count = to_write - put; 891 xput = ntfs_pwrite(vol->dev, xpos, count, xoutbuf); 892 if (xput == count) { 893 put += count; 894 xpos += count; 895 xoutbuf += count; 896 xrl++; 897 } 898 first = FALSE; 899 } while ((xput == count) && (put < to_write)); 900 return (put); 901} 902 903 904/* 905 * Compress and write a set of blocks 906 * 907 * returns the size actually written (rounded to a full cluster) 908 * or 0 if all zeroes (nothing is written) 909 * or -1 if could not compress (nothing is written) 910 * or -2 if there were an irrecoverable error (errno set) 911 */ 912 913static s32 ntfs_comp_set(ntfs_attr *na, runlist_element *rl, 914 s64 offs, u32 insz, const char *inbuf) 915{ 916 ntfs_volume *vol; 917 char *outbuf; 918 char *pbuf; 919 u32 compsz; 920 s32 written; 921 s32 rounded; 922 unsigned int clsz; 923 u32 p; 924 unsigned int sz; 925 unsigned int bsz; 926 BOOL fail; 927 BOOL allzeroes; 928 /* a single compressed zero */ 929 static char onezero[] = { 0x01, 0xb0, 0x00, 0x00 } ; 930 /* a couple of compressed zeroes */ 931 static char twozeroes[] = { 0x02, 0xb0, 0x00, 0x00, 0x00 } ; 932 /* more compressed zeroes, to be followed by some count */ 933 static char morezeroes[] = { 0x03, 0xb0, 0x02, 0x00 } ; 934 935 vol = na->ni->vol; 936 written = -1; /* default return */ 937 clsz = 1 << vol->cluster_size_bits; 938 /* may need 2 extra bytes per block and 2 more bytes */ 939 outbuf = (char*)ntfs_malloc(na->compression_block_size 940 + 2*(na->compression_block_size/NTFS_SB_SIZE) 941 + 2); 942 if (outbuf) { 943 fail = FALSE; 944 compsz = 0; 945 allzeroes = TRUE; 946 for (p=0; (p<insz) && !fail; p+=NTFS_SB_SIZE) { 947 if ((p + NTFS_SB_SIZE) < insz) 948 bsz = NTFS_SB_SIZE; 949 else 950 bsz = insz - p; 951 pbuf = &outbuf[compsz]; 952 sz = ntfs_compress_block(&inbuf[p],bsz,pbuf); 953 /* fail if all the clusters (or more) are needed */ 954 if (!sz || ((compsz + sz + clsz + 2) 955 > na->compression_block_size)) 956 fail = TRUE; 957 else { 958 if (allzeroes) { 959 /* check whether this is all zeroes */ 960 switch (sz) { 961 case 4 : 962 allzeroes = !memcmp( 963 pbuf,onezero,4); 964 break; 965 case 5 : 966 allzeroes = !memcmp( 967 pbuf,twozeroes,5); 968 break; 969 case 6 : 970 allzeroes = !memcmp( 971 pbuf,morezeroes,4); 972 break; 973 default : 974 allzeroes = FALSE; 975 break; 976 } 977 } 978 compsz += sz; 979 } 980 } 981 if (!fail && !allzeroes) { 982 /* add a couple of null bytes, space has been checked */ 983 outbuf[compsz++] = 0; 984 outbuf[compsz++] = 0; 985 /* write a full cluster, to avoid partial reading */ 986 rounded = ((compsz - 1) | (clsz - 1)) + 1; 987 written = write_clusters(vol, rl, offs, rounded, outbuf); 988 if (written != rounded) { 989 /* 990 * TODO : previously written text has been 991 * spoilt, should return a specific error 992 */ 993 ntfs_log_error("error writing compressed data\n"); 994 errno = EIO; 995 written = -2; 996 } 997 } else 998 if (!fail) 999 written = 0; 1000 free(outbuf); 1001 } 1002 return (written); 1003} 1004 1005/* 1006 * Check the validity of a compressed runlist 1007 * The check starts at the beginning of current run and ends 1008 * at the end of runlist 1009 * errno is set if the runlist is not valid 1010 */ 1011 1012static BOOL valid_compressed_run(ntfs_attr *na, runlist_element *rl, 1013 BOOL fullcheck, const char *text) 1014{ 1015 runlist_element *xrl; 1016 const char *err; 1017 BOOL ok = TRUE; 1018 1019 xrl = rl; 1020 while (xrl->vcn & (na->compression_block_clusters - 1)) 1021 xrl--; 1022 err = (const char*)NULL; 1023 while (xrl->length) { 1024 if ((xrl->vcn + xrl->length) != xrl[1].vcn) 1025 err = "Runs not adjacent"; 1026 if (xrl->lcn == LCN_HOLE) { 1027 if ((xrl->vcn + xrl->length) 1028 & (na->compression_block_clusters - 1)) { 1029 err = "Invalid hole"; 1030 } 1031 if (fullcheck && (xrl[1].lcn == LCN_HOLE)) { 1032 err = "Adjacent holes"; 1033 } 1034 } 1035 if (err) { 1036 ntfs_log_error("%s at %s index %ld inode %lld\n", 1037 err, text, (long)(xrl - na->rl), 1038 (long long)na->ni->mft_no); 1039 errno = EIO; 1040 ok = FALSE; 1041 err = (const char*)NULL; 1042 } 1043 xrl++; 1044 } 1045 return (ok); 1046} 1047 1048/* 1049 * Free unneeded clusters after overwriting compressed data 1050 * 1051 * This generally requires one or two empty slots at the end of runlist, 1052 * but we do not want to reallocate the runlist here because 1053 * there are many pointers to it. 1054 * So the empty slots have to be reserved beforehand 1055 * 1056 * Returns zero unless some error occurred (described by errno) 1057 * 1058 * +======= start of block =====+ 1059 * 0 |A chunk may overflow | <-- rl usedcnt : A + B 1060 * |A on previous block | then B 1061 * |A | 1062 * +-- end of allocated chunk --+ freelength : C 1063 * |B | (incl overflow) 1064 * +== end of compressed data ==+ 1065 * |C | <-- freerl freecnt : C + D 1066 * |C chunk may overflow | 1067 * |C on next block | 1068 * +-- end of allocated chunk --+ 1069 * |D | 1070 * |D chunk may overflow | 1071 * 15 |D on next block | 1072 * +======== end of block ======+ 1073 * 1074 */ 1075 1076static int ntfs_compress_overwr_free(ntfs_attr *na, runlist_element *rl, 1077 s32 usedcnt, s32 freecnt, VCN *update_from) 1078{ 1079 BOOL beginhole; 1080 BOOL mergeholes; 1081 s32 oldlength; 1082 s32 freelength; 1083 s64 freelcn; 1084 s64 freevcn; 1085 runlist_element *freerl; 1086 ntfs_volume *vol; 1087 s32 carry; 1088 int res; 1089 1090 vol = na->ni->vol; 1091 res = 0; 1092 freelcn = rl->lcn + usedcnt; 1093 freevcn = rl->vcn + usedcnt; 1094 freelength = rl->length - usedcnt; 1095 beginhole = !usedcnt && !rl->vcn; 1096 /* can merge with hole before ? */ 1097 mergeholes = !usedcnt 1098 && rl[0].vcn 1099 && (rl[-1].lcn == LCN_HOLE); 1100 /* truncate current run, carry to subsequent hole */ 1101 carry = freelength; 1102 oldlength = rl->length; 1103 if (mergeholes) { 1104 /* merging with a hole before */ 1105 freerl = rl; 1106 } else { 1107 rl->length -= freelength; /* warning : can be zero */ 1108 freerl = ++rl; 1109 } 1110 if (!mergeholes && (usedcnt || beginhole)) { 1111 s32 freed; 1112 runlist_element *frl; 1113 runlist_element *erl; 1114 int holes = 0; 1115 BOOL threeparts; 1116 1117 /* free the unneeded clusters from initial run, then freerl */ 1118 threeparts = (freelength > freecnt); 1119 freed = 0; 1120 frl = freerl; 1121 if (freelength) { 1122 res = ntfs_cluster_free_basic(vol,freelcn, 1123 (threeparts ? freecnt : freelength)); 1124 if (!res) 1125 freed += (threeparts ? freecnt : freelength); 1126 if (!usedcnt) { 1127 holes++; 1128 freerl--; 1129 freerl->length += (threeparts 1130 ? freecnt : freelength); 1131 if (freerl->vcn < *update_from) 1132 *update_from = freerl->vcn; 1133 } 1134 } 1135 while (!res && frl->length && (freed < freecnt)) { 1136 if (frl->length <= (freecnt - freed)) { 1137 res = ntfs_cluster_free_basic(vol, frl->lcn, 1138 frl->length); 1139 if (!res) { 1140 freed += frl->length; 1141 frl->lcn = LCN_HOLE; 1142 frl->length += carry; 1143 carry = 0; 1144 holes++; 1145 } 1146 } else { 1147 res = ntfs_cluster_free_basic(vol, frl->lcn, 1148 freecnt - freed); 1149 if (!res) { 1150 frl->lcn += freecnt - freed; 1151 frl->vcn += freecnt - freed; 1152 frl->length -= freecnt - freed; 1153 freed = freecnt; 1154 } 1155 } 1156 frl++; 1157 } 1158 na->compressed_size -= freed << vol->cluster_size_bits; 1159 switch (holes) { 1160 case 0 : 1161 /* there are no hole, must insert one */ 1162 /* space for hole has been prereserved */ 1163 if (freerl->lcn == LCN_HOLE) { 1164 if (threeparts) { 1165 erl = freerl; 1166 while (erl->length) 1167 erl++; 1168 do { 1169 erl[2] = *erl; 1170 } while (erl-- != freerl); 1171 1172 freerl[1].length = freelength - freecnt; 1173 freerl->length = freecnt; 1174 freerl[1].lcn = freelcn + freecnt; 1175 freerl[1].vcn = freevcn + freecnt; 1176 freerl[2].lcn = LCN_HOLE; 1177 freerl[2].vcn = freerl[1].vcn 1178 + freerl[1].length; 1179 freerl->vcn = freevcn; 1180 } else { 1181 freerl->vcn = freevcn; 1182 freerl->length += freelength; 1183 } 1184 } else { 1185 erl = freerl; 1186 while (erl->length) 1187 erl++; 1188 if (threeparts) { 1189 do { 1190 erl[2] = *erl; 1191 } while (erl-- != freerl); 1192 freerl[1].lcn = freelcn + freecnt; 1193 freerl[1].vcn = freevcn + freecnt; 1194 freerl[1].length = oldlength - usedcnt - freecnt; 1195 } else { 1196 do { 1197 erl[1] = *erl; 1198 } while (erl-- != freerl); 1199 } 1200 freerl->lcn = LCN_HOLE; 1201 freerl->vcn = freevcn; 1202 freerl->length = freecnt; 1203 } 1204 break; 1205 case 1 : 1206 /* there is a single hole, may have to merge */ 1207 freerl->vcn = freevcn; 1208 freerl->length = freecnt; 1209 if (freerl[1].lcn == LCN_HOLE) { 1210 freerl->length += freerl[1].length; 1211 erl = freerl; 1212 do { 1213 erl++; 1214 *erl = erl[1]; 1215 } while (erl->length); 1216 } 1217 break; 1218 default : 1219 /* there were several holes, must merge them */ 1220 freerl->lcn = LCN_HOLE; 1221 freerl->vcn = freevcn; 1222 freerl->length = freecnt; 1223 if (freerl[holes].lcn == LCN_HOLE) { 1224 freerl->length += freerl[holes].length; 1225 holes++; 1226 } 1227 erl = freerl; 1228 do { 1229 erl++; 1230 *erl = erl[holes - 1]; 1231 } while (erl->length); 1232 break; 1233 } 1234 } else { 1235 s32 freed; 1236 runlist_element *frl; 1237 runlist_element *xrl; 1238 1239 freed = 0; 1240 frl = freerl--; 1241 if (freerl->vcn < *update_from) 1242 *update_from = freerl->vcn; 1243 while (!res && frl->length && (freed < freecnt)) { 1244 if (frl->length <= (freecnt - freed)) { 1245 freerl->length += frl->length; 1246 freed += frl->length; 1247 res = ntfs_cluster_free_basic(vol, frl->lcn, 1248 frl->length); 1249 frl++; 1250 } else { 1251 freerl->length += freecnt - freed; 1252 res = ntfs_cluster_free_basic(vol, frl->lcn, 1253 freecnt - freed); 1254 frl->lcn += freecnt - freed; 1255 frl->vcn += freecnt - freed; 1256 frl->length -= freecnt - freed; 1257 freed = freecnt; 1258 } 1259 } 1260 /* remove unneded runlist entries */ 1261 xrl = freerl; 1262 /* group with next run if also a hole */ 1263 if (frl->length && (frl->lcn == LCN_HOLE)) { 1264 xrl->length += frl->length; 1265 frl++; 1266 } 1267 while (frl->length) { 1268 *++xrl = *frl++; 1269 } 1270 *++xrl = *frl; /* terminator */ 1271 na->compressed_size -= freed << vol->cluster_size_bits; 1272 } 1273 return (res); 1274} 1275 1276 1277/* 1278 * Free unneeded clusters after compression 1279 * 1280 * This generally requires one or two empty slots at the end of runlist, 1281 * but we do not want to reallocate the runlist here because 1282 * there are many pointers to it. 1283 * So the empty slots have to be reserved beforehand 1284 * 1285 * Returns zero unless some error occurred (described by errno) 1286 */ 1287 1288static int ntfs_compress_free(ntfs_attr *na, runlist_element *rl, 1289 s64 used, s64 reserved, BOOL appending, 1290 VCN *update_from) 1291{ 1292 s32 freecnt; 1293 s32 usedcnt; 1294 int res; 1295 s64 freelcn; 1296 s64 freevcn; 1297 s32 freelength; 1298 BOOL mergeholes; 1299 BOOL beginhole; 1300 ntfs_volume *vol; 1301 runlist_element *freerl; 1302 1303 res = -1; /* default return */ 1304 vol = na->ni->vol; 1305 freecnt = (reserved - used) >> vol->cluster_size_bits; 1306 usedcnt = (reserved >> vol->cluster_size_bits) - freecnt; 1307 if (rl->vcn < *update_from) 1308 *update_from = rl->vcn; 1309 /* skip entries fully used, if any */ 1310 while (rl->length && (rl->length < usedcnt)) { 1311 usedcnt -= rl->length; /* must be > 0 */ 1312 rl++; 1313 } 1314 if (rl->length) { 1315 /* 1316 * Splitting the current allocation block requires 1317 * an extra runlist element to create the hole. 1318 * The required entry has been prereserved when 1319 * mapping the runlist. 1320 */ 1321 /* get the free part in initial run */ 1322 freelcn = rl->lcn + usedcnt; 1323 freevcn = rl->vcn + usedcnt; 1324 /* new count of allocated clusters */ 1325 if (!((freevcn + freecnt) 1326 & (na->compression_block_clusters - 1))) { 1327 if (!appending) 1328 res = ntfs_compress_overwr_free(na,rl, 1329 usedcnt,freecnt,update_from); 1330 else { 1331 freelength = rl->length - usedcnt; 1332 beginhole = !usedcnt && !rl->vcn; 1333 mergeholes = !usedcnt 1334 && rl[0].vcn 1335 && (rl[-1].lcn == LCN_HOLE); 1336 if (mergeholes) { 1337 s32 carry; 1338 1339 /* shorten the runs which have free space */ 1340 carry = freecnt; 1341 freerl = rl; 1342 while (freerl->length < carry) { 1343 carry -= freerl->length; 1344 freerl++; 1345 } 1346 freerl->length = carry; 1347 freerl = rl; 1348 } else { 1349 rl->length = usedcnt; /* can be zero ? */ 1350 freerl = ++rl; 1351 } 1352 if ((freelength > 0) 1353 && !mergeholes 1354 && (usedcnt || beginhole)) { 1355 /* 1356 * move the unused part to the end. Doing so, 1357 * the vcn will be out of order. This does 1358 * not harm, the vcn are meaningless now, and 1359 * only the lcn are meaningful for freeing. 1360 */ 1361 /* locate current end */ 1362 while (rl->length) 1363 rl++; 1364 /* new terminator relocated */ 1365 rl[1].vcn = rl->vcn; 1366 rl[1].lcn = LCN_ENOENT; 1367 rl[1].length = 0; 1368 /* hole, currently allocated */ 1369 rl->vcn = freevcn; 1370 rl->lcn = freelcn; 1371 rl->length = freelength; 1372 } else { 1373 /* why is this different from the begin hole case ? */ 1374 if ((freelength > 0) 1375 && !mergeholes 1376 && !usedcnt) { 1377 freerl--; 1378 freerl->length = freelength; 1379 if (freerl->vcn < *update_from) 1380 *update_from 1381 = freerl->vcn; 1382 } 1383 } 1384 /* free the hole */ 1385 res = ntfs_cluster_free_from_rl(vol,freerl); 1386 if (!res) { 1387 na->compressed_size -= freecnt 1388 << vol->cluster_size_bits; 1389 if (mergeholes) { 1390 /* merge with adjacent hole */ 1391 freerl--; 1392 freerl->length += freecnt; 1393 } else { 1394 if (beginhole) 1395 freerl--; 1396 /* mark hole as free */ 1397 freerl->lcn = LCN_HOLE; 1398 freerl->vcn = freevcn; 1399 freerl->length = freecnt; 1400 } 1401 if (freerl->vcn < *update_from) 1402 *update_from = freerl->vcn; 1403 /* and set up the new end */ 1404 freerl[1].lcn = LCN_ENOENT; 1405 freerl[1].vcn = freevcn + freecnt; 1406 freerl[1].length = 0; 1407 } 1408 } 1409 } else { 1410 ntfs_log_error("Bad end of a compression block set\n"); 1411 errno = EIO; 1412 } 1413 } else { 1414 ntfs_log_error("No cluster to free after compression\n"); 1415 errno = EIO; 1416 } 1417 return (res); 1418} 1419 1420/* 1421 * Read existing data, decompress and append buffer 1422 * Do nothing if something fails 1423 */ 1424 1425static int ntfs_read_append(ntfs_attr *na, const runlist_element *rl, 1426 s64 offs, u32 compsz, s32 pos, BOOL appending, 1427 char *outbuf, s64 to_write, const void *b) 1428{ 1429 int fail = 1; 1430 char *compbuf; 1431 u32 decompsz; 1432 u32 got; 1433 1434 if (compsz == na->compression_block_size) { 1435 /* if the full block was requested, it was a hole */ 1436 memset(outbuf,0,compsz); 1437 memcpy(&outbuf[pos],b,to_write); 1438 fail = 0; 1439 } else { 1440 compbuf = (char*)ntfs_malloc(compsz); 1441 if (compbuf) { 1442 /* must align to full block for decompression */ 1443 if (appending) 1444 decompsz = ((pos - 1) | (NTFS_SB_SIZE - 1)) + 1; 1445 else 1446 decompsz = na->compression_block_size; 1447 got = read_clusters(na->ni->vol, rl, offs, 1448 compsz, compbuf); 1449 if ((got == compsz) 1450 && !ntfs_decompress((u8*)outbuf,decompsz, 1451 (u8*)compbuf,compsz)) { 1452 memcpy(&outbuf[pos],b,to_write); 1453 fail = 0; 1454 } 1455 free(compbuf); 1456 } 1457 } 1458 return (fail); 1459} 1460 1461/* 1462 * Flush a full compression block 1463 * 1464 * returns the size actually written (rounded to a full cluster) 1465 * or 0 if could not compress (and written uncompressed) 1466 * or -1 if there were an irrecoverable error (errno set) 1467 */ 1468 1469static s32 ntfs_flush(ntfs_attr *na, runlist_element *rl, s64 offs, 1470 const char *outbuf, s32 count, BOOL compress, 1471 BOOL appending, VCN *update_from) 1472{ 1473 s32 rounded; 1474 s32 written; 1475 int clsz; 1476 1477 if (compress) { 1478 written = ntfs_comp_set(na, rl, offs, count, outbuf); 1479 if (written == -1) 1480 compress = FALSE; 1481 if ((written >= 0) 1482 && ntfs_compress_free(na,rl,offs + written, 1483 offs + na->compression_block_size, appending, 1484 update_from)) 1485 written = -1; 1486 } else 1487 written = 0; 1488 if (!compress) { 1489 clsz = 1 << na->ni->vol->cluster_size_bits; 1490 rounded = ((count - 1) | (clsz - 1)) + 1; 1491 written = write_clusters(na->ni->vol, rl, 1492 offs, rounded, outbuf); 1493 if (written != rounded) 1494 written = -1; 1495 } 1496 return (written); 1497} 1498 1499/* 1500 * Write some data to be compressed. 1501 * Compression only occurs when a few clusters (usually 16) are 1502 * full. When this occurs an extra runlist slot may be needed, so 1503 * it has to be reserved beforehand. 1504 * 1505 * Returns the size of uncompressed data written, 1506 * or negative if an error occurred. 1507 * When the returned size is less than requested, new clusters have 1508 * to be allocated before the function is called again. 1509 */ 1510 1511s64 ntfs_compressed_pwrite(ntfs_attr *na, runlist_element *wrl, s64 wpos, 1512 s64 offs, s64 to_write, s64 rounded, 1513 const void *b, int compressed_part, 1514 VCN *update_from) 1515{ 1516 ntfs_volume *vol; 1517 runlist_element *brl; /* entry containing the beginning of block */ 1518 int compression_length; 1519 s64 written; 1520 s64 to_read; 1521 s64 to_flush; 1522 s64 roffs; 1523 s64 got; 1524 s64 start_vcn; 1525 s64 nextblock; 1526 s64 endwrite; 1527 u32 compsz; 1528 char *inbuf; 1529 char *outbuf; 1530 BOOL fail; 1531 BOOL done; 1532 BOOL compress; 1533 BOOL appending; 1534 1535 if (!valid_compressed_run(na,wrl,FALSE,"begin compressed write")) { 1536 return (-1); 1537 } 1538 if ((*update_from < 0) 1539 || (compressed_part < 0) 1540 || (compressed_part > (int)na->compression_block_clusters)) { 1541 ntfs_log_error("Bad update vcn or compressed_part %d for compressed write\n", 1542 compressed_part); 1543 errno = EIO; 1544 return (-1); 1545 } 1546 /* make sure there are two unused entries in runlist */ 1547 if (na->unused_runs < 2) { 1548 ntfs_log_error("No unused runs for compressed write\n"); 1549 errno = EIO; 1550 return (-1); 1551 } 1552 if (wrl->vcn < *update_from) 1553 *update_from = wrl->vcn; 1554 written = -1; /* default return */ 1555 vol = na->ni->vol; 1556 compression_length = na->compression_block_clusters; 1557 compress = FALSE; 1558 done = FALSE; 1559 /* 1560 * Cannot accept writing beyond the current compression set 1561 * because when compression occurs, clusters are freed 1562 * and have to be reallocated. 1563 * (cannot happen with standard fuse 4K buffers) 1564 * Caller has to avoid this situation, or face consequences. 1565 */ 1566 nextblock = ((offs + (wrl->vcn << vol->cluster_size_bits)) 1567 | (na->compression_block_size - 1)) + 1; 1568 /* determine whether we are appending to file */ 1569 endwrite = offs + to_write + (wrl->vcn << vol->cluster_size_bits); 1570 appending = endwrite >= na->initialized_size; 1571 if (endwrite >= nextblock) { 1572 /* it is time to compress */ 1573 compress = TRUE; 1574 /* only process what we can */ 1575 to_write = rounded = nextblock 1576 - (offs + (wrl->vcn << vol->cluster_size_bits)); 1577 } 1578 start_vcn = 0; 1579 fail = FALSE; 1580 brl = wrl; 1581 roffs = 0; 1582 /* 1583 * If we are about to compress or we need to decompress 1584 * existing data, we have to process a full set of blocks. 1585 * So relocate the parameters to the beginning of allocation 1586 * containing the first byte of the set of blocks. 1587 */ 1588 if (compress || compressed_part) { 1589 /* find the beginning of block */ 1590 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits)) 1591 & -compression_length; 1592 if (start_vcn < *update_from) 1593 *update_from = start_vcn; 1594 while (brl->vcn && (brl->vcn > start_vcn)) { 1595 /* jumping back a hole means big trouble */ 1596 if (brl->lcn == (LCN)LCN_HOLE) { 1597 ntfs_log_error("jump back over a hole when appending\n"); 1598 fail = TRUE; 1599 errno = EIO; 1600 } 1601 brl--; 1602 offs += brl->length << vol->cluster_size_bits; 1603 } 1604 roffs = (start_vcn - brl->vcn) << vol->cluster_size_bits; 1605 } 1606 if (compressed_part && !fail) { 1607 /* 1608 * The set of compression blocks contains compressed data 1609 * (we are reopening an existing file to append to it) 1610 * Decompress the data and append 1611 */ 1612 compsz = (s32)compressed_part << vol->cluster_size_bits; 1613 outbuf = (char*)ntfs_malloc(na->compression_block_size); 1614 if (outbuf) { 1615 if (appending) { 1616 to_read = offs - roffs; 1617 to_flush = to_read + to_write; 1618 } else { 1619 to_read = na->data_size 1620 - (brl->vcn << vol->cluster_size_bits); 1621 if (to_read > na->compression_block_size) 1622 to_read = na->compression_block_size; 1623 to_flush = to_read; 1624 } 1625 if (!ntfs_read_append(na, brl, roffs, compsz, 1626 (s32)(offs - roffs), appending, 1627 outbuf, to_write, b)) { 1628 written = ntfs_flush(na, brl, roffs, 1629 outbuf, to_flush, compress, appending, 1630 update_from); 1631 if (written >= 0) { 1632 written = to_write; 1633 done = TRUE; 1634 } 1635 } 1636 free(outbuf); 1637 } 1638 } else { 1639 if (compress && !fail) { 1640 /* 1641 * we are filling up a block, read the full set 1642 * of blocks and compress it 1643 */ 1644 inbuf = (char*)ntfs_malloc(na->compression_block_size); 1645 if (inbuf) { 1646 to_read = offs - roffs; 1647 if (to_read) 1648 got = read_clusters(vol, brl, roffs, 1649 to_read, inbuf); 1650 else 1651 got = 0; 1652 if (got == to_read) { 1653 memcpy(&inbuf[to_read],b,to_write); 1654 written = ntfs_comp_set(na, brl, roffs, 1655 to_read + to_write, inbuf); 1656 /* 1657 * if compression was not successful, 1658 * only write the part which was requested 1659 */ 1660 if ((written >= 0) 1661 /* free the unused clusters */ 1662 && !ntfs_compress_free(na,brl, 1663 written + roffs, 1664 na->compression_block_size 1665 + roffs, 1666 appending, update_from)) { 1667 done = TRUE; 1668 written = to_write; 1669 } 1670 } 1671 free(inbuf); 1672 } 1673 } 1674 if (!done) { 1675 /* 1676 * if the compression block is not full, or 1677 * if compression failed for whatever reason, 1678 * write uncompressed 1679 */ 1680 /* check we are not overflowing current allocation */ 1681 if ((wpos + rounded) 1682 > ((wrl->lcn + wrl->length) 1683 << vol->cluster_size_bits)) { 1684 ntfs_log_error("writing on unallocated clusters\n"); 1685 errno = EIO; 1686 } else { 1687 written = ntfs_pwrite(vol->dev, wpos, 1688 rounded, b); 1689 if (written == rounded) 1690 written = to_write; 1691 } 1692 } 1693 } 1694 if ((written >= 0) 1695 && !valid_compressed_run(na,wrl,TRUE,"end compressed write")) 1696 written = -1; 1697 return (written); 1698} 1699 1700/* 1701 * Close a file written compressed. 1702 * This compresses the last partial compression block of the file. 1703 * Two empty runlist slots have to be reserved beforehand. 1704 * 1705 * Returns zero if closing is successful. 1706 */ 1707 1708int ntfs_compressed_close(ntfs_attr *na, runlist_element *wrl, s64 offs, 1709 VCN *update_from) 1710{ 1711 ntfs_volume *vol; 1712 runlist_element *brl; /* entry containing the beginning of block */ 1713 int compression_length; 1714 s64 written; 1715 s64 to_read; 1716 s64 roffs; 1717 s64 got; 1718 s64 start_vcn; 1719 char *inbuf; 1720 BOOL fail; 1721 BOOL done; 1722 1723 if (na->unused_runs < 2) { 1724 ntfs_log_error("No unused runs for compressed close\n"); 1725 errno = EIO; 1726 return (-1); 1727 } 1728 if (*update_from < 0) { 1729 ntfs_log_error("Bad update vcn for compressed close\n"); 1730 errno = EIO; 1731 return (-1); 1732 } 1733 if (wrl->vcn < *update_from) 1734 *update_from = wrl->vcn; 1735 vol = na->ni->vol; 1736 compression_length = na->compression_block_clusters; 1737 done = FALSE; 1738 /* 1739 * There generally is an uncompressed block at end of file, 1740 * read the full block and compress it 1741 */ 1742 inbuf = (char*)ntfs_malloc(na->compression_block_size); 1743 if (inbuf) { 1744 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits)) 1745 & -compression_length; 1746 if (start_vcn < *update_from) 1747 *update_from = start_vcn; 1748 to_read = offs + ((wrl->vcn - start_vcn) 1749 << vol->cluster_size_bits); 1750 brl = wrl; 1751 fail = FALSE; 1752 while (brl->vcn && (brl->vcn > start_vcn)) { 1753 if (brl->lcn == (LCN)LCN_HOLE) { 1754 ntfs_log_error("jump back over a hole when closing\n"); 1755 fail = TRUE; 1756 errno = EIO; 1757 } 1758 brl--; 1759 } 1760 if (!fail) { 1761 /* roffs can be an offset from another uncomp block */ 1762 roffs = (start_vcn - brl->vcn) 1763 << vol->cluster_size_bits; 1764 if (to_read) { 1765 got = read_clusters(vol, brl, roffs, to_read, 1766 inbuf); 1767 if (got == to_read) { 1768 written = ntfs_comp_set(na, brl, roffs, 1769 to_read, inbuf); 1770 if ((written >= 0) 1771 /* free the unused clusters */ 1772 && !ntfs_compress_free(na,brl, 1773 written + roffs, 1774 na->compression_block_size + roffs, 1775 TRUE, update_from)) { 1776 done = TRUE; 1777 } else 1778 /* if compression failed, leave uncompressed */ 1779 if (written == -1) 1780 done = TRUE; 1781 } 1782 } else 1783 done = TRUE; 1784 free(inbuf); 1785 } 1786 } 1787 if (done && !valid_compressed_run(na,wrl,TRUE,"end compressed close")) 1788 done = FALSE; 1789 return (!done); 1790} 1791