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-2013 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 */ 72 typedef 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 84 struct 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 107 static 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 191 static 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 */ 320 static 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); 340 do_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; 388 do_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; 483 return_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 */ 504 static 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 */ 512 restart: 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 */ 563 s64 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; 653 do_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 u32 decompsz; 738 739 /* 740 * Compressed cb, decompress it into the temporary buffer, then 741 * copy the data to the destination range overlapping the cb. 742 */ 743 ntfs_log_debug("Found compressed compression block.\n"); 744 /* 745 * Read the compressed data into the temporary buffer. 746 * NOTE: We cheat a little bit here by marking the attribute as 747 * not compressed in the ntfs_attr structure so that we can 748 * read the raw, compressed data by simply using 749 * ntfs_attr_pread(). (-8 750 * NOTE: We have to modify data_size and initialized_size 751 * temporarily as well... 752 */ 753 to_read = cb_size; 754 NAttrClearCompressed(na); 755 na->data_flags &= ~ATTR_COMPRESSION_MASK; 756 tdata_size = na->data_size; 757 tinitialized_size = na->initialized_size; 758 na->data_size = na->initialized_size = na->allocated_size; 759 do { 760 br = ntfs_attr_pread(na, 761 (vcn << vol->cluster_size_bits) + 762 (cb_pos - cb), to_read, cb_pos); 763 if (br <= 0) { 764 if (!br) { 765 ntfs_log_error("Failed to read a" 766 " compressed cluster, " 767 " inode %lld offs 0x%llx\n", 768 (long long)na->ni->mft_no, 769 (long long)(vcn << vol->cluster_size_bits)); 770 errno = EIO; 771 } 772 err = errno; 773 na->data_size = tdata_size; 774 na->initialized_size = tinitialized_size; 775 na->ni->flags |= compression; 776 na->data_flags = data_flags; 777 free(cb); 778 free(dest); 779 if (total) 780 return total; 781 errno = err; 782 return br; 783 } 784 cb_pos += br; 785 to_read -= br; 786 } while (to_read > 0); 787 na->data_size = tdata_size; 788 na->initialized_size = tinitialized_size; 789 na->ni->flags |= compression; 790 na->data_flags = data_flags; 791 /* Just a precaution. */ 792 if (cb_pos + 2 <= cb_end) 793 *(u16*)cb_pos = 0; 794 ntfs_log_debug("Successfully read the compression block.\n"); 795 /* Do not decompress beyond the requested block */ 796 to_read = min(count, cb_size - ofs); 797 decompsz = ((ofs + to_read - 1) | (NTFS_SB_SIZE - 1)) + 1; 798 if (ntfs_decompress(dest, decompsz, cb, cb_size) < 0) { 799 err = errno; 800 free(cb); 801 free(dest); 802 if (total) 803 return total; 804 errno = err; 805 return -1; 806 } 807 memcpy(b, dest + ofs, to_read); 808 total += to_read; 809 count -= to_read; 810 b = (u8*)b + to_read; 811 ofs = 0; 812 } 813 /* Do we have more work to do? */ 814 if (nr_cbs) 815 goto do_next_cb; 816 /* We no longer need the buffers. */ 817 free(cb); 818 free(dest); 819 /* Return number of bytes read. */ 820 return total + total2; 821 } 822 823 /* 824 * Read data from a set of clusters 825 * 826 * Returns the amount of data read 827 */ 828 829 static u32 read_clusters(ntfs_volume *vol, const runlist_element *rl, 830 s64 offs, u32 to_read, char *inbuf) 831 { 832 u32 count; 833 int xgot; 834 u32 got; 835 s64 xpos; 836 BOOL first; 837 char *xinbuf; 838 const runlist_element *xrl; 839 840 got = 0; 841 xrl = rl; 842 xinbuf = inbuf; 843 first = TRUE; 844 do { 845 count = xrl->length << vol->cluster_size_bits; 846 xpos = xrl->lcn << vol->cluster_size_bits; 847 if (first) { 848 count -= offs; 849 xpos += offs; 850 } 851 if ((to_read - got) < count) 852 count = to_read - got; 853 xgot = ntfs_pread(vol->dev, xpos, count, xinbuf); 854 if (xgot == (int)count) { 855 got += count; 856 xpos += count; 857 xinbuf += count; 858 xrl++; 859 } 860 first = FALSE; 861 } while ((xgot == (int)count) && (got < to_read)); 862 return (got); 863 } 864 865 /* 866 * Write data to a set of clusters 867 * 868 * Returns the amount of data written 869 */ 870 871 static s32 write_clusters(ntfs_volume *vol, const runlist_element *rl, 872 s64 offs, s32 to_write, const char *outbuf) 873 { 874 s32 count; 875 s32 put, xput; 876 s64 xpos; 877 BOOL first; 878 const char *xoutbuf; 879 const runlist_element *xrl; 880 881 put = 0; 882 xrl = rl; 883 xoutbuf = outbuf; 884 first = TRUE; 885 do { 886 count = xrl->length << vol->cluster_size_bits; 887 xpos = xrl->lcn << vol->cluster_size_bits; 888 if (first) { 889 count -= offs; 890 xpos += offs; 891 } 892 if ((to_write - put) < count) 893 count = to_write - put; 894 xput = ntfs_pwrite(vol->dev, xpos, count, xoutbuf); 895 if (xput == count) { 896 put += count; 897 xpos += count; 898 xoutbuf += count; 899 xrl++; 900 } 901 first = FALSE; 902 } while ((xput == count) && (put < to_write)); 903 return (put); 904 } 905 906 907 /* 908 * Compress and write a set of blocks 909 * 910 * returns the size actually written (rounded to a full cluster) 911 * or 0 if all zeroes (nothing is written) 912 * or -1 if could not compress (nothing is written) 913 * or -2 if there were an irrecoverable error (errno set) 914 */ 915 916 static s32 ntfs_comp_set(ntfs_attr *na, runlist_element *rl, 917 s64 offs, u32 insz, const char *inbuf) 918 { 919 ntfs_volume *vol; 920 char *outbuf; 921 char *pbuf; 922 u32 compsz; 923 s32 written; 924 s32 rounded; 925 unsigned int clsz; 926 u32 p; 927 unsigned int sz; 928 unsigned int bsz; 929 BOOL fail; 930 BOOL allzeroes; 931 /* a single compressed zero */ 932 static char onezero[] = { 0x01, 0xb0, 0x00, 0x00 } ; 933 /* a couple of compressed zeroes */ 934 static char twozeroes[] = { 0x02, 0xb0, 0x00, 0x00, 0x00 } ; 935 /* more compressed zeroes, to be followed by some count */ 936 static char morezeroes[] = { 0x03, 0xb0, 0x02, 0x00 } ; 937 938 vol = na->ni->vol; 939 written = -1; /* default return */ 940 clsz = 1 << vol->cluster_size_bits; 941 /* may need 2 extra bytes per block and 2 more bytes */ 942 outbuf = (char*)ntfs_malloc(na->compression_block_size 943 + 2*(na->compression_block_size/NTFS_SB_SIZE) 944 + 2); 945 if (outbuf) { 946 fail = FALSE; 947 compsz = 0; 948 allzeroes = TRUE; 949 for (p=0; (p<insz) && !fail; p+=NTFS_SB_SIZE) { 950 if ((p + NTFS_SB_SIZE) < insz) 951 bsz = NTFS_SB_SIZE; 952 else 953 bsz = insz - p; 954 pbuf = &outbuf[compsz]; 955 sz = ntfs_compress_block(&inbuf[p],bsz,pbuf); 956 /* fail if all the clusters (or more) are needed */ 957 if (!sz || ((compsz + sz + clsz + 2) 958 > na->compression_block_size)) 959 fail = TRUE; 960 else { 961 if (allzeroes) { 962 /* check whether this is all zeroes */ 963 switch (sz) { 964 case 4 : 965 allzeroes = !memcmp( 966 pbuf,onezero,4); 967 break; 968 case 5 : 969 allzeroes = !memcmp( 970 pbuf,twozeroes,5); 971 break; 972 case 6 : 973 allzeroes = !memcmp( 974 pbuf,morezeroes,4); 975 break; 976 default : 977 allzeroes = FALSE; 978 break; 979 } 980 } 981 compsz += sz; 982 } 983 } 984 if (!fail && !allzeroes) { 985 /* add a couple of null bytes, space has been checked */ 986 outbuf[compsz++] = 0; 987 outbuf[compsz++] = 0; 988 /* write a full cluster, to avoid partial reading */ 989 rounded = ((compsz - 1) | (clsz - 1)) + 1; 990 written = write_clusters(vol, rl, offs, rounded, outbuf); 991 if (written != rounded) { 992 /* 993 * TODO : previously written text has been 994 * spoilt, should return a specific error 995 */ 996 ntfs_log_error("error writing compressed data\n"); 997 errno = EIO; 998 written = -2; 999 } 1000 } else 1001 if (!fail) 1002 written = 0; 1003 free(outbuf); 1004 } 1005 return (written); 1006 } 1007 1008 /* 1009 * Check the validity of a compressed runlist 1010 * The check starts at the beginning of current run and ends 1011 * at the end of runlist 1012 * errno is set if the runlist is not valid 1013 */ 1014 1015 static BOOL valid_compressed_run(ntfs_attr *na, runlist_element *rl, 1016 BOOL fullcheck, const char *text) 1017 { 1018 runlist_element *xrl; 1019 const char *err; 1020 BOOL ok = TRUE; 1021 1022 xrl = rl; 1023 while (xrl->vcn & (na->compression_block_clusters - 1)) 1024 xrl--; 1025 err = (const char*)NULL; 1026 while (xrl->length) { 1027 if ((xrl->vcn + xrl->length) != xrl[1].vcn) 1028 err = "Runs not adjacent"; 1029 if (xrl->lcn == LCN_HOLE) { 1030 if ((xrl->vcn + xrl->length) 1031 & (na->compression_block_clusters - 1)) { 1032 err = "Invalid hole"; 1033 } 1034 if (fullcheck && (xrl[1].lcn == LCN_HOLE)) { 1035 err = "Adjacent holes"; 1036 } 1037 } 1038 if (err) { 1039 ntfs_log_error("%s at %s index %ld inode %lld\n", 1040 err, text, (long)(xrl - na->rl), 1041 (long long)na->ni->mft_no); 1042 errno = EIO; 1043 ok = FALSE; 1044 err = (const char*)NULL; 1045 } 1046 xrl++; 1047 } 1048 return (ok); 1049 } 1050 1051 /* 1052 * Free unneeded clusters after overwriting compressed data 1053 * 1054 * This generally requires one or two empty slots at the end of runlist, 1055 * but we do not want to reallocate the runlist here because 1056 * there are many pointers to it. 1057 * So the empty slots have to be reserved beforehand 1058 * 1059 * Returns zero unless some error occurred (described by errno) 1060 * 1061 * +======= start of block =====+ 1062 * 0 |A chunk may overflow | <-- rl usedcnt : A + B 1063 * |A on previous block | then B 1064 * |A | 1065 * +-- end of allocated chunk --+ freelength : C 1066 * |B | (incl overflow) 1067 * +== end of compressed data ==+ 1068 * |C | <-- freerl freecnt : C + D 1069 * |C chunk may overflow | 1070 * |C on next block | 1071 * +-- end of allocated chunk --+ 1072 * |D | 1073 * |D chunk may overflow | 1074 * 15 |D on next block | 1075 * +======== end of block ======+ 1076 * 1077 */ 1078 1079 static int ntfs_compress_overwr_free(ntfs_attr *na, runlist_element *rl, 1080 s32 usedcnt, s32 freecnt, VCN *update_from) 1081 { 1082 BOOL beginhole; 1083 BOOL mergeholes; 1084 s32 oldlength; 1085 s32 freelength; 1086 s64 freelcn; 1087 s64 freevcn; 1088 runlist_element *freerl; 1089 ntfs_volume *vol; 1090 s32 carry; 1091 int res; 1092 1093 vol = na->ni->vol; 1094 res = 0; 1095 freelcn = rl->lcn + usedcnt; 1096 freevcn = rl->vcn + usedcnt; 1097 freelength = rl->length - usedcnt; 1098 beginhole = !usedcnt && !rl->vcn; 1099 /* can merge with hole before ? */ 1100 mergeholes = !usedcnt 1101 && rl[0].vcn 1102 && (rl[-1].lcn == LCN_HOLE); 1103 /* truncate current run, carry to subsequent hole */ 1104 carry = freelength; 1105 oldlength = rl->length; 1106 if (mergeholes) { 1107 /* merging with a hole before */ 1108 freerl = rl; 1109 } else { 1110 rl->length -= freelength; /* warning : can be zero */ 1111 freerl = ++rl; 1112 } 1113 if (!mergeholes && (usedcnt || beginhole)) { 1114 s32 freed; 1115 runlist_element *frl; 1116 runlist_element *erl; 1117 int holes = 0; 1118 BOOL threeparts; 1119 1120 /* free the unneeded clusters from initial run, then freerl */ 1121 threeparts = (freelength > freecnt); 1122 freed = 0; 1123 frl = freerl; 1124 if (freelength) { 1125 res = ntfs_cluster_free_basic(vol,freelcn, 1126 (threeparts ? freecnt : freelength)); 1127 if (!res) 1128 freed += (threeparts ? freecnt : freelength); 1129 if (!usedcnt) { 1130 holes++; 1131 freerl--; 1132 freerl->length += (threeparts 1133 ? freecnt : freelength); 1134 if (freerl->vcn < *update_from) 1135 *update_from = freerl->vcn; 1136 } 1137 } 1138 while (!res && frl->length && (freed < freecnt)) { 1139 if (frl->length <= (freecnt - freed)) { 1140 res = ntfs_cluster_free_basic(vol, frl->lcn, 1141 frl->length); 1142 if (!res) { 1143 freed += frl->length; 1144 frl->lcn = LCN_HOLE; 1145 frl->length += carry; 1146 carry = 0; 1147 holes++; 1148 } 1149 } else { 1150 res = ntfs_cluster_free_basic(vol, frl->lcn, 1151 freecnt - freed); 1152 if (!res) { 1153 frl->lcn += freecnt - freed; 1154 frl->vcn += freecnt - freed; 1155 frl->length -= freecnt - freed; 1156 freed = freecnt; 1157 } 1158 } 1159 frl++; 1160 } 1161 na->compressed_size -= freed << vol->cluster_size_bits; 1162 switch (holes) { 1163 case 0 : 1164 /* there are no hole, must insert one */ 1165 /* space for hole has been prereserved */ 1166 if (freerl->lcn == LCN_HOLE) { 1167 if (threeparts) { 1168 erl = freerl; 1169 while (erl->length) 1170 erl++; 1171 do { 1172 erl[2] = *erl; 1173 } while (erl-- != freerl); 1174 1175 freerl[1].length = freelength - freecnt; 1176 freerl->length = freecnt; 1177 freerl[1].lcn = freelcn + freecnt; 1178 freerl[1].vcn = freevcn + freecnt; 1179 freerl[2].lcn = LCN_HOLE; 1180 freerl[2].vcn = freerl[1].vcn 1181 + freerl[1].length; 1182 freerl->vcn = freevcn; 1183 } else { 1184 freerl->vcn = freevcn; 1185 freerl->length += freelength; 1186 } 1187 } else { 1188 erl = freerl; 1189 while (erl->length) 1190 erl++; 1191 if (threeparts) { 1192 do { 1193 erl[2] = *erl; 1194 } while (erl-- != freerl); 1195 freerl[1].lcn = freelcn + freecnt; 1196 freerl[1].vcn = freevcn + freecnt; 1197 freerl[1].length = oldlength - usedcnt - freecnt; 1198 } else { 1199 do { 1200 erl[1] = *erl; 1201 } while (erl-- != freerl); 1202 } 1203 freerl->lcn = LCN_HOLE; 1204 freerl->vcn = freevcn; 1205 freerl->length = freecnt; 1206 } 1207 break; 1208 case 1 : 1209 /* there is a single hole, may have to merge */ 1210 freerl->vcn = freevcn; 1211 freerl->length = freecnt; 1212 if (freerl[1].lcn == LCN_HOLE) { 1213 freerl->length += freerl[1].length; 1214 erl = freerl; 1215 do { 1216 erl++; 1217 *erl = erl[1]; 1218 } while (erl->length); 1219 } 1220 break; 1221 default : 1222 /* there were several holes, must merge them */ 1223 freerl->lcn = LCN_HOLE; 1224 freerl->vcn = freevcn; 1225 freerl->length = freecnt; 1226 if (freerl[holes].lcn == LCN_HOLE) { 1227 freerl->length += freerl[holes].length; 1228 holes++; 1229 } 1230 erl = freerl; 1231 do { 1232 erl++; 1233 *erl = erl[holes - 1]; 1234 } while (erl->length); 1235 break; 1236 } 1237 } else { 1238 s32 freed; 1239 runlist_element *frl; 1240 runlist_element *xrl; 1241 1242 freed = 0; 1243 frl = freerl--; 1244 if (freerl->vcn < *update_from) 1245 *update_from = freerl->vcn; 1246 while (!res && frl->length && (freed < freecnt)) { 1247 if (frl->length <= (freecnt - freed)) { 1248 freerl->length += frl->length; 1249 freed += frl->length; 1250 res = ntfs_cluster_free_basic(vol, frl->lcn, 1251 frl->length); 1252 frl++; 1253 } else { 1254 freerl->length += freecnt - freed; 1255 res = ntfs_cluster_free_basic(vol, frl->lcn, 1256 freecnt - freed); 1257 frl->lcn += freecnt - freed; 1258 frl->vcn += freecnt - freed; 1259 frl->length -= freecnt - freed; 1260 freed = freecnt; 1261 } 1262 } 1263 /* remove unneded runlist entries */ 1264 xrl = freerl; 1265 /* group with next run if also a hole */ 1266 if (frl->length && (frl->lcn == LCN_HOLE)) { 1267 xrl->length += frl->length; 1268 frl++; 1269 } 1270 while (frl->length) { 1271 *++xrl = *frl++; 1272 } 1273 *++xrl = *frl; /* terminator */ 1274 na->compressed_size -= freed << vol->cluster_size_bits; 1275 } 1276 return (res); 1277 } 1278 1279 1280 /* 1281 * Free unneeded clusters after compression 1282 * 1283 * This generally requires one or two empty slots at the end of runlist, 1284 * but we do not want to reallocate the runlist here because 1285 * there are many pointers to it. 1286 * So the empty slots have to be reserved beforehand 1287 * 1288 * Returns zero unless some error occurred (described by errno) 1289 */ 1290 1291 static int ntfs_compress_free(ntfs_attr *na, runlist_element *rl, 1292 s64 used, s64 reserved, BOOL appending, 1293 VCN *update_from) 1294 { 1295 s32 freecnt; 1296 s32 usedcnt; 1297 int res; 1298 s64 freelcn; 1299 s64 freevcn; 1300 s32 freelength; 1301 BOOL mergeholes; 1302 BOOL beginhole; 1303 ntfs_volume *vol; 1304 runlist_element *freerl; 1305 1306 res = -1; /* default return */ 1307 vol = na->ni->vol; 1308 freecnt = (reserved - used) >> vol->cluster_size_bits; 1309 usedcnt = (reserved >> vol->cluster_size_bits) - freecnt; 1310 if (rl->vcn < *update_from) 1311 *update_from = rl->vcn; 1312 /* skip entries fully used, if any */ 1313 while (rl->length && (rl->length < usedcnt)) { 1314 usedcnt -= rl->length; /* must be > 0 */ 1315 rl++; 1316 } 1317 if (rl->length) { 1318 /* 1319 * Splitting the current allocation block requires 1320 * an extra runlist element to create the hole. 1321 * The required entry has been prereserved when 1322 * mapping the runlist. 1323 */ 1324 /* get the free part in initial run */ 1325 freelcn = rl->lcn + usedcnt; 1326 freevcn = rl->vcn + usedcnt; 1327 /* new count of allocated clusters */ 1328 if (!((freevcn + freecnt) 1329 & (na->compression_block_clusters - 1))) { 1330 if (!appending) 1331 res = ntfs_compress_overwr_free(na,rl, 1332 usedcnt,freecnt,update_from); 1333 else { 1334 freelength = rl->length - usedcnt; 1335 beginhole = !usedcnt && !rl->vcn; 1336 mergeholes = !usedcnt 1337 && rl[0].vcn 1338 && (rl[-1].lcn == LCN_HOLE); 1339 if (mergeholes) { 1340 s32 carry; 1341 1342 /* shorten the runs which have free space */ 1343 carry = freecnt; 1344 freerl = rl; 1345 while (freerl->length < carry) { 1346 carry -= freerl->length; 1347 freerl++; 1348 } 1349 freerl->length = carry; 1350 freerl = rl; 1351 } else { 1352 rl->length = usedcnt; /* can be zero ? */ 1353 freerl = ++rl; 1354 } 1355 if ((freelength > 0) 1356 && !mergeholes 1357 && (usedcnt || beginhole)) { 1358 /* 1359 * move the unused part to the end. Doing so, 1360 * the vcn will be out of order. This does 1361 * not harm, the vcn are meaningless now, and 1362 * only the lcn are meaningful for freeing. 1363 */ 1364 /* locate current end */ 1365 while (rl->length) 1366 rl++; 1367 /* new terminator relocated */ 1368 rl[1].vcn = rl->vcn; 1369 rl[1].lcn = LCN_ENOENT; 1370 rl[1].length = 0; 1371 /* hole, currently allocated */ 1372 rl->vcn = freevcn; 1373 rl->lcn = freelcn; 1374 rl->length = freelength; 1375 } else { 1376 /* why is this different from the begin hole case ? */ 1377 if ((freelength > 0) 1378 && !mergeholes 1379 && !usedcnt) { 1380 freerl--; 1381 freerl->length = freelength; 1382 if (freerl->vcn < *update_from) 1383 *update_from 1384 = freerl->vcn; 1385 } 1386 } 1387 /* free the hole */ 1388 res = ntfs_cluster_free_from_rl(vol,freerl); 1389 if (!res) { 1390 na->compressed_size -= freecnt 1391 << vol->cluster_size_bits; 1392 if (mergeholes) { 1393 /* merge with adjacent hole */ 1394 freerl--; 1395 freerl->length += freecnt; 1396 } else { 1397 if (beginhole) 1398 freerl--; 1399 /* mark hole as free */ 1400 freerl->lcn = LCN_HOLE; 1401 freerl->vcn = freevcn; 1402 freerl->length = freecnt; 1403 } 1404 if (freerl->vcn < *update_from) 1405 *update_from = freerl->vcn; 1406 /* and set up the new end */ 1407 freerl[1].lcn = LCN_ENOENT; 1408 freerl[1].vcn = freevcn + freecnt; 1409 freerl[1].length = 0; 1410 } 1411 } 1412 } else { 1413 ntfs_log_error("Bad end of a compression block set\n"); 1414 errno = EIO; 1415 } 1416 } else { 1417 ntfs_log_error("No cluster to free after compression\n"); 1418 errno = EIO; 1419 } 1420 return (res); 1421 } 1422 1423 /* 1424 * Read existing data, decompress and append buffer 1425 * Do nothing if something fails 1426 */ 1427 1428 static int ntfs_read_append(ntfs_attr *na, const runlist_element *rl, 1429 s64 offs, u32 compsz, s32 pos, BOOL appending, 1430 char *outbuf, s64 to_write, const void *b) 1431 { 1432 int fail = 1; 1433 char *compbuf; 1434 u32 decompsz; 1435 u32 got; 1436 1437 if (compsz == na->compression_block_size) { 1438 /* if the full block was requested, it was a hole */ 1439 memset(outbuf,0,compsz); 1440 memcpy(&outbuf[pos],b,to_write); 1441 fail = 0; 1442 } else { 1443 compbuf = (char*)ntfs_malloc(compsz); 1444 if (compbuf) { 1445 /* must align to full block for decompression */ 1446 if (appending) 1447 decompsz = ((pos - 1) | (NTFS_SB_SIZE - 1)) + 1; 1448 else 1449 decompsz = na->compression_block_size; 1450 got = read_clusters(na->ni->vol, rl, offs, 1451 compsz, compbuf); 1452 if ((got == compsz) 1453 && !ntfs_decompress((u8*)outbuf,decompsz, 1454 (u8*)compbuf,compsz)) { 1455 memcpy(&outbuf[pos],b,to_write); 1456 fail = 0; 1457 } 1458 free(compbuf); 1459 } 1460 } 1461 return (fail); 1462 } 1463 1464 /* 1465 * Flush a full compression block 1466 * 1467 * returns the size actually written (rounded to a full cluster) 1468 * or 0 if could not compress (and written uncompressed) 1469 * or -1 if there were an irrecoverable error (errno set) 1470 */ 1471 1472 static s32 ntfs_flush(ntfs_attr *na, runlist_element *rl, s64 offs, 1473 const char *outbuf, s32 count, BOOL compress, 1474 BOOL appending, VCN *update_from) 1475 { 1476 s32 rounded; 1477 s32 written; 1478 int clsz; 1479 1480 if (compress) { 1481 written = ntfs_comp_set(na, rl, offs, count, outbuf); 1482 if (written == -1) 1483 compress = FALSE; 1484 if ((written >= 0) 1485 && ntfs_compress_free(na,rl,offs + written, 1486 offs + na->compression_block_size, appending, 1487 update_from)) 1488 written = -1; 1489 } else 1490 written = 0; 1491 if (!compress) { 1492 clsz = 1 << na->ni->vol->cluster_size_bits; 1493 rounded = ((count - 1) | (clsz - 1)) + 1; 1494 written = write_clusters(na->ni->vol, rl, 1495 offs, rounded, outbuf); 1496 if (written != rounded) 1497 written = -1; 1498 } 1499 return (written); 1500 } 1501 1502 /* 1503 * Write some data to be compressed. 1504 * Compression only occurs when a few clusters (usually 16) are 1505 * full. When this occurs an extra runlist slot may be needed, so 1506 * it has to be reserved beforehand. 1507 * 1508 * Returns the size of uncompressed data written, 1509 * or negative if an error occurred. 1510 * When the returned size is less than requested, new clusters have 1511 * to be allocated before the function is called again. 1512 */ 1513 1514 s64 ntfs_compressed_pwrite(ntfs_attr *na, runlist_element *wrl, s64 wpos, 1515 s64 offs, s64 to_write, s64 rounded, 1516 const void *b, int compressed_part, 1517 VCN *update_from) 1518 { 1519 ntfs_volume *vol; 1520 runlist_element *brl; /* entry containing the beginning of block */ 1521 int compression_length; 1522 s64 written; 1523 s64 to_read; 1524 s64 to_flush; 1525 s64 roffs; 1526 s64 got; 1527 s64 start_vcn; 1528 s64 nextblock; 1529 s64 endwrite; 1530 u32 compsz; 1531 char *inbuf; 1532 char *outbuf; 1533 BOOL fail; 1534 BOOL done; 1535 BOOL compress; 1536 BOOL appending; 1537 1538 if (!valid_compressed_run(na,wrl,FALSE,"begin compressed write")) { 1539 return (-1); 1540 } 1541 if ((*update_from < 0) 1542 || (compressed_part < 0) 1543 || (compressed_part > (int)na->compression_block_clusters)) { 1544 ntfs_log_error("Bad update vcn or compressed_part %d for compressed write\n", 1545 compressed_part); 1546 errno = EIO; 1547 return (-1); 1548 } 1549 /* make sure there are two unused entries in runlist */ 1550 if (na->unused_runs < 2) { 1551 ntfs_log_error("No unused runs for compressed write\n"); 1552 errno = EIO; 1553 return (-1); 1554 } 1555 if (wrl->vcn < *update_from) 1556 *update_from = wrl->vcn; 1557 written = -1; /* default return */ 1558 vol = na->ni->vol; 1559 compression_length = na->compression_block_clusters; 1560 compress = FALSE; 1561 done = FALSE; 1562 /* 1563 * Cannot accept writing beyond the current compression set 1564 * because when compression occurs, clusters are freed 1565 * and have to be reallocated. 1566 * (cannot happen with standard fuse 4K buffers) 1567 * Caller has to avoid this situation, or face consequences. 1568 */ 1569 nextblock = ((offs + (wrl->vcn << vol->cluster_size_bits)) 1570 | (na->compression_block_size - 1)) + 1; 1571 /* determine whether we are appending to file */ 1572 endwrite = offs + to_write + (wrl->vcn << vol->cluster_size_bits); 1573 appending = endwrite >= na->initialized_size; 1574 if (endwrite >= nextblock) { 1575 /* it is time to compress */ 1576 compress = TRUE; 1577 /* only process what we can */ 1578 to_write = rounded = nextblock 1579 - (offs + (wrl->vcn << vol->cluster_size_bits)); 1580 } 1581 start_vcn = 0; 1582 fail = FALSE; 1583 brl = wrl; 1584 roffs = 0; 1585 /* 1586 * If we are about to compress or we need to decompress 1587 * existing data, we have to process a full set of blocks. 1588 * So relocate the parameters to the beginning of allocation 1589 * containing the first byte of the set of blocks. 1590 */ 1591 if (compress || compressed_part) { 1592 /* find the beginning of block */ 1593 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits)) 1594 & -compression_length; 1595 if (start_vcn < *update_from) 1596 *update_from = start_vcn; 1597 while (brl->vcn && (brl->vcn > start_vcn)) { 1598 /* jumping back a hole means big trouble */ 1599 if (brl->lcn == (LCN)LCN_HOLE) { 1600 ntfs_log_error("jump back over a hole when appending\n"); 1601 fail = TRUE; 1602 errno = EIO; 1603 } 1604 brl--; 1605 offs += brl->length << vol->cluster_size_bits; 1606 } 1607 roffs = (start_vcn - brl->vcn) << vol->cluster_size_bits; 1608 } 1609 if (compressed_part && !fail) { 1610 /* 1611 * The set of compression blocks contains compressed data 1612 * (we are reopening an existing file to append to it) 1613 * Decompress the data and append 1614 */ 1615 compsz = (s32)compressed_part << vol->cluster_size_bits; 1616 outbuf = (char*)ntfs_malloc(na->compression_block_size); 1617 if (outbuf) { 1618 if (appending) { 1619 to_read = offs - roffs; 1620 to_flush = to_read + to_write; 1621 } else { 1622 to_read = na->data_size 1623 - (brl->vcn << vol->cluster_size_bits); 1624 if (to_read > na->compression_block_size) 1625 to_read = na->compression_block_size; 1626 to_flush = to_read; 1627 } 1628 if (!ntfs_read_append(na, brl, roffs, compsz, 1629 (s32)(offs - roffs), appending, 1630 outbuf, to_write, b)) { 1631 written = ntfs_flush(na, brl, roffs, 1632 outbuf, to_flush, compress, appending, 1633 update_from); 1634 if (written >= 0) { 1635 written = to_write; 1636 done = TRUE; 1637 } 1638 } 1639 free(outbuf); 1640 } 1641 } else { 1642 if (compress && !fail) { 1643 /* 1644 * we are filling up a block, read the full set 1645 * of blocks and compress it 1646 */ 1647 inbuf = (char*)ntfs_malloc(na->compression_block_size); 1648 if (inbuf) { 1649 to_read = offs - roffs; 1650 if (to_read) 1651 got = read_clusters(vol, brl, roffs, 1652 to_read, inbuf); 1653 else 1654 got = 0; 1655 if (got == to_read) { 1656 memcpy(&inbuf[to_read],b,to_write); 1657 written = ntfs_comp_set(na, brl, roffs, 1658 to_read + to_write, inbuf); 1659 /* 1660 * if compression was not successful, 1661 * only write the part which was requested 1662 */ 1663 if ((written >= 0) 1664 /* free the unused clusters */ 1665 && !ntfs_compress_free(na,brl, 1666 written + roffs, 1667 na->compression_block_size 1668 + roffs, 1669 appending, update_from)) { 1670 done = TRUE; 1671 written = to_write; 1672 } 1673 } 1674 free(inbuf); 1675 } 1676 } 1677 if (!done) { 1678 /* 1679 * if the compression block is not full, or 1680 * if compression failed for whatever reason, 1681 * write uncompressed 1682 */ 1683 /* check we are not overflowing current allocation */ 1684 if ((wpos + rounded) 1685 > ((wrl->lcn + wrl->length) 1686 << vol->cluster_size_bits)) { 1687 ntfs_log_error("writing on unallocated clusters\n"); 1688 errno = EIO; 1689 } else { 1690 written = ntfs_pwrite(vol->dev, wpos, 1691 rounded, b); 1692 if (written == rounded) 1693 written = to_write; 1694 } 1695 } 1696 } 1697 if ((written >= 0) 1698 && !valid_compressed_run(na,wrl,TRUE,"end compressed write")) 1699 written = -1; 1700 return (written); 1701 } 1702 1703 /* 1704 * Close a file written compressed. 1705 * This compresses the last partial compression block of the file. 1706 * Two empty runlist slots have to be reserved beforehand. 1707 * 1708 * Returns zero if closing is successful. 1709 */ 1710 1711 int ntfs_compressed_close(ntfs_attr *na, runlist_element *wrl, s64 offs, 1712 VCN *update_from) 1713 { 1714 ntfs_volume *vol; 1715 runlist_element *brl; /* entry containing the beginning of block */ 1716 int compression_length; 1717 s64 written; 1718 s64 to_read; 1719 s64 roffs; 1720 s64 got; 1721 s64 start_vcn; 1722 char *inbuf; 1723 BOOL fail; 1724 BOOL done; 1725 1726 if (na->unused_runs < 2) { 1727 ntfs_log_error("No unused runs for compressed close\n"); 1728 errno = EIO; 1729 return (-1); 1730 } 1731 if (*update_from < 0) { 1732 ntfs_log_error("Bad update vcn for compressed close\n"); 1733 errno = EIO; 1734 return (-1); 1735 } 1736 if (wrl->vcn < *update_from) 1737 *update_from = wrl->vcn; 1738 vol = na->ni->vol; 1739 compression_length = na->compression_block_clusters; 1740 done = FALSE; 1741 /* 1742 * There generally is an uncompressed block at end of file, 1743 * read the full block and compress it 1744 */ 1745 inbuf = (char*)ntfs_malloc(na->compression_block_size); 1746 if (inbuf) { 1747 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits)) 1748 & -compression_length; 1749 if (start_vcn < *update_from) 1750 *update_from = start_vcn; 1751 to_read = offs + ((wrl->vcn - start_vcn) 1752 << vol->cluster_size_bits); 1753 brl = wrl; 1754 fail = FALSE; 1755 while (brl->vcn && (brl->vcn > start_vcn)) { 1756 if (brl->lcn == (LCN)LCN_HOLE) { 1757 ntfs_log_error("jump back over a hole when closing\n"); 1758 fail = TRUE; 1759 errno = EIO; 1760 } 1761 brl--; 1762 } 1763 if (!fail) { 1764 /* roffs can be an offset from another uncomp block */ 1765 roffs = (start_vcn - brl->vcn) 1766 << vol->cluster_size_bits; 1767 if (to_read) { 1768 got = read_clusters(vol, brl, roffs, to_read, 1769 inbuf); 1770 if (got == to_read) { 1771 written = ntfs_comp_set(na, brl, roffs, 1772 to_read, inbuf); 1773 if ((written >= 0) 1774 /* free the unused clusters */ 1775 && !ntfs_compress_free(na,brl, 1776 written + roffs, 1777 na->compression_block_size + roffs, 1778 TRUE, update_from)) { 1779 done = TRUE; 1780 } else 1781 /* if compression failed, leave uncompressed */ 1782 if (written == -1) 1783 done = TRUE; 1784 } 1785 } else 1786 done = TRUE; 1787 free(inbuf); 1788 } 1789 } 1790 if (done && !valid_compressed_run(na,wrl,TRUE,"end compressed close")) 1791 done = FALSE; 1792 return (!done); 1793 } 1794