1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <linux/fs.h>
25#include <linux/buffer_head.h>
26#include <linux/blkdev.h>
27#include <linux/vmalloc.h>
28#include <linux/slab.h>
29
30#include "attrib.h"
31#include "inode.h"
32#include "debug.h"
33#include "ntfs.h"
34
35
36
37
38typedef enum {
39
40 NTFS_SYMBOL_TOKEN = 0,
41 NTFS_PHRASE_TOKEN = 1,
42 NTFS_TOKEN_MASK = 1,
43
44
45 NTFS_SB_SIZE_MASK = 0x0fff,
46 NTFS_SB_SIZE = 0x1000,
47 NTFS_SB_IS_COMPRESSED = 0x8000,
48
49
50
51
52
53
54
55 NTFS_MAX_CB_SIZE = 64 * 1024,
56} ntfs_compression_constants;
57
58
59
60
61static u8 *ntfs_compression_buffer;
62
63
64
65
66static DEFINE_SPINLOCK(ntfs_cb_lock);
67
68
69
70
71
72
73
74
75int allocate_compression_buffers(void)
76{
77 BUG_ON(ntfs_compression_buffer);
78
79 ntfs_compression_buffer = vmalloc(NTFS_MAX_CB_SIZE);
80 if (!ntfs_compression_buffer)
81 return -ENOMEM;
82 return 0;
83}
84
85
86
87
88
89
90void free_compression_buffers(void)
91{
92 BUG_ON(!ntfs_compression_buffer);
93 vfree(ntfs_compression_buffer);
94 ntfs_compression_buffer = NULL;
95}
96
97
98
99
100static void zero_partial_compressed_page(struct page *page,
101 const s64 initialized_size)
102{
103 u8 *kp = page_address(page);
104 unsigned int kp_ofs;
105
106 ntfs_debug("Zeroing page region outside initialized size.");
107 if (((s64)page->index << PAGE_SHIFT) >= initialized_size) {
108 clear_page(kp);
109 return;
110 }
111 kp_ofs = initialized_size & ~PAGE_MASK;
112 memset(kp + kp_ofs, 0, PAGE_SIZE - kp_ofs);
113 return;
114}
115
116
117
118
119static inline void handle_bounds_compressed_page(struct page *page,
120 const loff_t i_size, const s64 initialized_size)
121{
122 if ((page->index >= (initialized_size >> PAGE_SHIFT)) &&
123 (initialized_size < i_size))
124 zero_partial_compressed_page(page, initialized_size);
125 return;
126}
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165static int ntfs_decompress(struct page *dest_pages[], int *dest_index,
166 int *dest_ofs, const int dest_max_index, const int dest_max_ofs,
167 const int xpage, char *xpage_done, u8 *const cb_start,
168 const u32 cb_size, const loff_t i_size,
169 const s64 initialized_size)
170{
171
172
173
174
175 u8 *cb_end = cb_start + cb_size;
176 u8 *cb = cb_start;
177 u8 *cb_sb_start = cb;
178 u8 *cb_sb_end;
179
180
181 struct page *dp;
182 u8 *dp_addr;
183 u8 *dp_sb_start;
184 u8 *dp_sb_end;
185
186 u16 do_sb_start;
187 u16 do_sb_end;
188
189
190
191 u8 tag;
192 int token;
193
194
195 int completed_pages[dest_max_index - *dest_index + 1];
196 int nr_completed_pages = 0;
197
198
199 int err = -EOVERFLOW;
200
201 ntfs_debug("Entering, cb_size = 0x%x.", cb_size);
202do_next_sb:
203 ntfs_debug("Beginning sub-block at offset = 0x%zx in the cb.",
204 cb - cb_start);
205
206
207
208
209
210
211 if (cb == cb_end || !le16_to_cpup((le16*)cb) ||
212 (*dest_index == dest_max_index &&
213 *dest_ofs == dest_max_ofs)) {
214 int i;
215
216 ntfs_debug("Completed. Returning success (0).");
217 err = 0;
218return_error:
219
220 spin_unlock(&ntfs_cb_lock);
221
222 if (nr_completed_pages > 0) {
223 for (i = 0; i < nr_completed_pages; i++) {
224 int di = completed_pages[i];
225
226 dp = dest_pages[di];
227
228
229
230
231 handle_bounds_compressed_page(dp, i_size,
232 initialized_size);
233 flush_dcache_page(dp);
234 kunmap(dp);
235 SetPageUptodate(dp);
236 unlock_page(dp);
237 if (di == xpage)
238 *xpage_done = 1;
239 else
240 put_page(dp);
241 dest_pages[di] = NULL;
242 }
243 }
244 return err;
245 }
246
247
248 do_sb_start = *dest_ofs;
249 do_sb_end = do_sb_start + NTFS_SB_SIZE;
250
251
252 if (*dest_index == dest_max_index && do_sb_end > dest_max_ofs)
253 goto return_overflow;
254
255
256 if (cb + 6 > cb_end)
257 goto return_overflow;
258
259
260 cb_sb_start = cb;
261 cb_sb_end = cb_sb_start + (le16_to_cpup((le16*)cb) & NTFS_SB_SIZE_MASK)
262 + 3;
263 if (cb_sb_end > cb_end)
264 goto return_overflow;
265
266
267 dp = dest_pages[*dest_index];
268 if (!dp) {
269
270 cb = cb_sb_end;
271
272
273 *dest_ofs = (*dest_ofs + NTFS_SB_SIZE) & ~PAGE_MASK;
274 if (!*dest_ofs && (++*dest_index > dest_max_index))
275 goto return_overflow;
276 goto do_next_sb;
277 }
278
279
280 dp_addr = (u8*)page_address(dp) + do_sb_start;
281
282
283 if (!(le16_to_cpup((le16*)cb) & NTFS_SB_IS_COMPRESSED)) {
284 ntfs_debug("Found uncompressed sub-block.");
285
286
287
288 cb += 2;
289
290
291 if (cb_sb_end - cb != NTFS_SB_SIZE)
292 goto return_overflow;
293
294
295 memcpy(dp_addr, cb, NTFS_SB_SIZE);
296 cb += NTFS_SB_SIZE;
297
298
299 *dest_ofs += NTFS_SB_SIZE;
300 if (!(*dest_ofs &= ~PAGE_MASK)) {
301finalize_page:
302
303
304
305
306 completed_pages[nr_completed_pages++] = *dest_index;
307 if (++*dest_index > dest_max_index)
308 goto return_overflow;
309 }
310 goto do_next_sb;
311 }
312 ntfs_debug("Found compressed sub-block.");
313
314
315
316 dp_sb_start = dp_addr;
317 dp_sb_end = dp_sb_start + NTFS_SB_SIZE;
318
319
320 cb += 2;
321do_next_tag:
322 if (cb == cb_sb_end) {
323
324 if (dp_addr < dp_sb_end) {
325 int nr_bytes = do_sb_end - *dest_ofs;
326
327 ntfs_debug("Filling incomplete sub-block with "
328 "zeroes.");
329
330 memset(dp_addr, 0, nr_bytes);
331 *dest_ofs += nr_bytes;
332 }
333
334 if (!(*dest_ofs &= ~PAGE_MASK))
335 goto finalize_page;
336 goto do_next_sb;
337 }
338
339
340 if (cb > cb_sb_end || dp_addr > dp_sb_end)
341 goto return_overflow;
342
343
344 tag = *cb++;
345
346
347 for (token = 0; token < 8; token++, tag >>= 1) {
348 u16 lg, pt, length, max_non_overlap;
349 register u16 i;
350 u8 *dp_back_addr;
351
352
353 if (cb >= cb_sb_end || dp_addr > dp_sb_end)
354 break;
355
356
357 if ((tag & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) {
358
359
360
361
362 *dp_addr++ = *cb++;
363 ++*dest_ofs;
364
365
366 continue;
367 }
368
369
370
371
372
373 if (dp_addr == dp_sb_start)
374 goto return_overflow;
375
376
377
378
379
380
381
382
383 lg = 0;
384 for (i = *dest_ofs - do_sb_start - 1; i >= 0x10; i >>= 1)
385 lg++;
386
387
388 pt = le16_to_cpup((le16*)cb);
389
390
391
392
393
394
395 dp_back_addr = dp_addr - (pt >> (12 - lg)) - 1;
396 if (dp_back_addr < dp_sb_start)
397 goto return_overflow;
398
399
400 length = (pt & (0xfff >> lg)) + 3;
401
402
403 *dest_ofs += length;
404 if (*dest_ofs > do_sb_end)
405 goto return_overflow;
406
407
408 max_non_overlap = dp_addr - dp_back_addr;
409
410 if (length <= max_non_overlap) {
411
412 memcpy(dp_addr, dp_back_addr, length);
413
414
415 dp_addr += length;
416 } else {
417
418
419
420
421
422
423 memcpy(dp_addr, dp_back_addr, max_non_overlap);
424 dp_addr += max_non_overlap;
425 dp_back_addr += max_non_overlap;
426 length -= max_non_overlap;
427 while (length--)
428 *dp_addr++ = *dp_back_addr++;
429 }
430
431
432 cb += 2;
433 }
434
435
436 goto do_next_tag;
437
438return_overflow:
439 ntfs_error(NULL, "Failed. Returning -EOVERFLOW.");
440 goto return_error;
441}
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478int ntfs_read_compressed_block(struct page *page)
479{
480 loff_t i_size;
481 s64 initialized_size;
482 struct address_space *mapping = page->mapping;
483 ntfs_inode *ni = NTFS_I(mapping->host);
484 ntfs_volume *vol = ni->vol;
485 struct super_block *sb = vol->sb;
486 runlist_element *rl;
487 unsigned long flags, block_size = sb->s_blocksize;
488 unsigned char block_size_bits = sb->s_blocksize_bits;
489 u8 *cb, *cb_pos, *cb_end;
490 struct buffer_head **bhs;
491 unsigned long offset, index = page->index;
492 u32 cb_size = ni->itype.compressed.block_size;
493 u64 cb_size_mask = cb_size - 1UL;
494 VCN vcn;
495 LCN lcn;
496
497 VCN start_vcn = (((s64)index << PAGE_SHIFT) & ~cb_size_mask) >>
498 vol->cluster_size_bits;
499
500
501
502
503 VCN end_vcn = ((((s64)(index + 1UL) << PAGE_SHIFT) + cb_size - 1)
504 & ~cb_size_mask) >> vol->cluster_size_bits;
505
506 unsigned int nr_cbs = (end_vcn - start_vcn) << vol->cluster_size_bits
507 >> ni->itype.compressed.block_size_bits;
508
509
510
511
512
513 unsigned int nr_pages = (end_vcn - start_vcn) <<
514 vol->cluster_size_bits >> PAGE_SHIFT;
515 unsigned int xpage, max_page, cur_page, cur_ofs, i;
516 unsigned int cb_clusters, cb_max_ofs;
517 int block, max_block, cb_max_page, bhs_size, nr_bhs, err = 0;
518 struct page **pages;
519 unsigned char xpage_done = 0;
520
521 ntfs_debug("Entering, page->index = 0x%lx, cb_size = 0x%x, nr_pages = "
522 "%i.", index, cb_size, nr_pages);
523
524
525
526
527 BUG_ON(ni->type != AT_DATA);
528 BUG_ON(ni->name_len);
529
530 pages = kmalloc(nr_pages * sizeof(struct page *), GFP_NOFS);
531
532
533 bhs_size = cb_size / block_size * sizeof(struct buffer_head *);
534 bhs = kmalloc(bhs_size, GFP_NOFS);
535
536 if (unlikely(!pages || !bhs)) {
537 kfree(bhs);
538 kfree(pages);
539 unlock_page(page);
540 ntfs_error(vol->sb, "Failed to allocate internal buffers.");
541 return -ENOMEM;
542 }
543
544
545
546
547
548 offset = start_vcn << vol->cluster_size_bits >> PAGE_SHIFT;
549 xpage = index - offset;
550 pages[xpage] = page;
551
552
553
554
555 read_lock_irqsave(&ni->size_lock, flags);
556 i_size = i_size_read(VFS_I(ni));
557 initialized_size = ni->initialized_size;
558 read_unlock_irqrestore(&ni->size_lock, flags);
559 max_page = ((i_size + PAGE_SIZE - 1) >> PAGE_SHIFT) -
560 offset;
561
562 if (xpage >= max_page) {
563 kfree(bhs);
564 kfree(pages);
565 zero_user(page, 0, PAGE_SIZE);
566 ntfs_debug("Compressed read outside i_size - truncated?");
567 SetPageUptodate(page);
568 unlock_page(page);
569 return 0;
570 }
571 if (nr_pages < max_page)
572 max_page = nr_pages;
573 for (i = 0; i < max_page; i++, offset++) {
574 if (i != xpage)
575 pages[i] = grab_cache_page_nowait(mapping, offset);
576 page = pages[i];
577 if (page) {
578
579
580
581
582
583 if (!PageDirty(page) && (!PageUptodate(page) ||
584 PageError(page))) {
585 ClearPageError(page);
586 kmap(page);
587 continue;
588 }
589 unlock_page(page);
590 put_page(page);
591 pages[i] = NULL;
592 }
593 }
594
595
596
597
598
599 cur_page = 0;
600 cur_ofs = 0;
601 cb_clusters = ni->itype.compressed.block_clusters;
602do_next_cb:
603 nr_cbs--;
604 nr_bhs = 0;
605
606
607 rl = NULL;
608 for (vcn = start_vcn, start_vcn += cb_clusters; vcn < start_vcn;
609 vcn++) {
610 bool is_retry = false;
611
612 if (!rl) {
613lock_retry_remap:
614 down_read(&ni->runlist.lock);
615 rl = ni->runlist.rl;
616 }
617 if (likely(rl != NULL)) {
618
619 while (rl->length && rl[1].vcn <= vcn)
620 rl++;
621 lcn = ntfs_rl_vcn_to_lcn(rl, vcn);
622 } else
623 lcn = LCN_RL_NOT_MAPPED;
624 ntfs_debug("Reading vcn = 0x%llx, lcn = 0x%llx.",
625 (unsigned long long)vcn,
626 (unsigned long long)lcn);
627 if (lcn < 0) {
628
629
630
631
632 if (lcn == LCN_HOLE)
633 break;
634 if (is_retry || lcn != LCN_RL_NOT_MAPPED)
635 goto rl_err;
636 is_retry = true;
637
638
639
640
641 up_read(&ni->runlist.lock);
642 if (!ntfs_map_runlist(ni, vcn))
643 goto lock_retry_remap;
644 goto map_rl_err;
645 }
646 block = lcn << vol->cluster_size_bits >> block_size_bits;
647
648 max_block = block + (vol->cluster_size >> block_size_bits);
649 do {
650 ntfs_debug("block = 0x%x.", block);
651 if (unlikely(!(bhs[nr_bhs] = sb_getblk(sb, block))))
652 goto getblk_err;
653 nr_bhs++;
654 } while (++block < max_block);
655 }
656
657
658 if (rl)
659 up_read(&ni->runlist.lock);
660
661
662 for (i = 0; i < nr_bhs; i++) {
663 struct buffer_head *tbh = bhs[i];
664
665 if (!trylock_buffer(tbh))
666 continue;
667 if (unlikely(buffer_uptodate(tbh))) {
668 unlock_buffer(tbh);
669 continue;
670 }
671 get_bh(tbh);
672 tbh->b_end_io = end_buffer_read_sync;
673 submit_bh(REQ_OP_READ, 0, tbh);
674 }
675
676
677 for (i = 0; i < nr_bhs; i++) {
678 struct buffer_head *tbh = bhs[i];
679
680 if (buffer_uptodate(tbh))
681 continue;
682 wait_on_buffer(tbh);
683
684
685
686
687
688
689
690
691 barrier();
692 if (unlikely(!buffer_uptodate(tbh))) {
693 ntfs_warning(vol->sb, "Buffer is unlocked but not "
694 "uptodate! Unplugging the disk queue "
695 "and rescheduling.");
696 get_bh(tbh);
697 io_schedule();
698 put_bh(tbh);
699 if (unlikely(!buffer_uptodate(tbh)))
700 goto read_err;
701 ntfs_warning(vol->sb, "Buffer is now uptodate. Good.");
702 }
703 }
704
705
706
707
708
709 spin_lock(&ntfs_cb_lock);
710 cb = ntfs_compression_buffer;
711
712 BUG_ON(!cb);
713
714 cb_pos = cb;
715 cb_end = cb + cb_size;
716
717
718 for (i = 0; i < nr_bhs; i++) {
719 memcpy(cb_pos, bhs[i]->b_data, block_size);
720 cb_pos += block_size;
721 }
722
723
724 if (cb_pos + 2 <= cb + cb_size)
725 *(u16*)cb_pos = 0;
726
727
728 cb_pos = cb;
729
730
731 ntfs_debug("Successfully read the compression block.");
732
733
734 cb_max_page = (cur_page << PAGE_SHIFT) + cur_ofs + cb_size;
735 cb_max_ofs = cb_max_page & ~PAGE_MASK;
736 cb_max_page >>= PAGE_SHIFT;
737
738
739 if (cb_max_page > max_page)
740 cb_max_page = max_page;
741
742 if (vcn == start_vcn - cb_clusters) {
743
744 ntfs_debug("Found sparse compression block.");
745
746 spin_unlock(&ntfs_cb_lock);
747 if (cb_max_ofs)
748 cb_max_page--;
749 for (; cur_page < cb_max_page; cur_page++) {
750 page = pages[cur_page];
751 if (page) {
752 if (likely(!cur_ofs))
753 clear_page(page_address(page));
754 else
755 memset(page_address(page) + cur_ofs, 0,
756 PAGE_SIZE -
757 cur_ofs);
758 flush_dcache_page(page);
759 kunmap(page);
760 SetPageUptodate(page);
761 unlock_page(page);
762 if (cur_page == xpage)
763 xpage_done = 1;
764 else
765 put_page(page);
766 pages[cur_page] = NULL;
767 }
768 cb_pos += PAGE_SIZE - cur_ofs;
769 cur_ofs = 0;
770 if (cb_pos >= cb_end)
771 break;
772 }
773
774 if (cb_max_ofs && cb_pos < cb_end) {
775 page = pages[cur_page];
776 if (page)
777 memset(page_address(page) + cur_ofs, 0,
778 cb_max_ofs - cur_ofs);
779
780
781
782
783 cur_ofs = cb_max_ofs;
784 }
785 } else if (vcn == start_vcn) {
786
787 unsigned int cur2_page = cur_page;
788 unsigned int cur_ofs2 = cur_ofs;
789 u8 *cb_pos2 = cb_pos;
790
791 ntfs_debug("Found uncompressed compression block.");
792
793
794
795
796
797
798
799
800
801
802
803 if (cb_max_ofs)
804 cb_max_page--;
805
806 for (; cur_page < cb_max_page; cur_page++) {
807 page = pages[cur_page];
808 if (page)
809 memcpy(page_address(page) + cur_ofs, cb_pos,
810 PAGE_SIZE - cur_ofs);
811 cb_pos += PAGE_SIZE - cur_ofs;
812 cur_ofs = 0;
813 if (cb_pos >= cb_end)
814 break;
815 }
816
817 if (cb_max_ofs && cb_pos < cb_end) {
818 page = pages[cur_page];
819 if (page)
820 memcpy(page_address(page) + cur_ofs, cb_pos,
821 cb_max_ofs - cur_ofs);
822 cb_pos += cb_max_ofs - cur_ofs;
823 cur_ofs = cb_max_ofs;
824 }
825
826 spin_unlock(&ntfs_cb_lock);
827
828 for (; cur2_page < cb_max_page; cur2_page++) {
829 page = pages[cur2_page];
830 if (page) {
831
832
833
834
835 handle_bounds_compressed_page(page, i_size,
836 initialized_size);
837 flush_dcache_page(page);
838 kunmap(page);
839 SetPageUptodate(page);
840 unlock_page(page);
841 if (cur2_page == xpage)
842 xpage_done = 1;
843 else
844 put_page(page);
845 pages[cur2_page] = NULL;
846 }
847 cb_pos2 += PAGE_SIZE - cur_ofs2;
848 cur_ofs2 = 0;
849 if (cb_pos2 >= cb_end)
850 break;
851 }
852 } else {
853
854 unsigned int prev_cur_page = cur_page;
855
856 ntfs_debug("Found compressed compression block.");
857 err = ntfs_decompress(pages, &cur_page, &cur_ofs,
858 cb_max_page, cb_max_ofs, xpage, &xpage_done,
859 cb_pos, cb_size - (cb_pos - cb), i_size,
860 initialized_size);
861
862
863
864
865 if (err) {
866 ntfs_error(vol->sb, "ntfs_decompress() failed in inode "
867 "0x%lx with error code %i. Skipping "
868 "this compression block.",
869 ni->mft_no, -err);
870
871 for (; prev_cur_page < cur_page; prev_cur_page++) {
872 page = pages[prev_cur_page];
873 if (page) {
874 flush_dcache_page(page);
875 kunmap(page);
876 unlock_page(page);
877 if (prev_cur_page != xpage)
878 put_page(page);
879 pages[prev_cur_page] = NULL;
880 }
881 }
882 }
883 }
884
885
886 for (i = 0; i < nr_bhs; i++)
887 brelse(bhs[i]);
888
889
890 if (nr_cbs)
891 goto do_next_cb;
892
893
894 kfree(bhs);
895
896
897 for (cur_page = 0; cur_page < max_page; cur_page++) {
898 page = pages[cur_page];
899 if (page) {
900 ntfs_error(vol->sb, "Still have pages left! "
901 "Terminating them with extreme "
902 "prejudice. Inode 0x%lx, page index "
903 "0x%lx.", ni->mft_no, page->index);
904 flush_dcache_page(page);
905 kunmap(page);
906 unlock_page(page);
907 if (cur_page != xpage)
908 put_page(page);
909 pages[cur_page] = NULL;
910 }
911 }
912
913
914 kfree(pages);
915
916
917 if (likely(xpage_done))
918 return 0;
919
920 ntfs_debug("Failed. Returning error code %s.", err == -EOVERFLOW ?
921 "EOVERFLOW" : (!err ? "EIO" : "unknown error"));
922 return err < 0 ? err : -EIO;
923
924read_err:
925 ntfs_error(vol->sb, "IO error while reading compressed data.");
926
927 for (i = 0; i < nr_bhs; i++)
928 brelse(bhs[i]);
929 goto err_out;
930
931map_rl_err:
932 ntfs_error(vol->sb, "ntfs_map_runlist() failed. Cannot read "
933 "compression block.");
934 goto err_out;
935
936rl_err:
937 up_read(&ni->runlist.lock);
938 ntfs_error(vol->sb, "ntfs_rl_vcn_to_lcn() failed. Cannot read "
939 "compression block.");
940 goto err_out;
941
942getblk_err:
943 up_read(&ni->runlist.lock);
944 ntfs_error(vol->sb, "getblk() failed. Cannot read compression block.");
945
946err_out:
947 kfree(bhs);
948 for (i = cur_page; i < max_page; i++) {
949 page = pages[i];
950 if (page) {
951 flush_dcache_page(page);
952 kunmap(page);
953 unlock_page(page);
954 if (i != xpage)
955 put_page(page);
956 }
957 }
958 kfree(pages);
959 return -EIO;
960}
961