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