1/*-
2 * Copyright (c) 2010-2012 Michihiro NAKAJIMA
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25#include "test.h"
26__FBSDID("$FreeBSD$");
27
28#ifdef HAVE_SYS_IOCTL_H
29#include <sys/ioctl.h>
30#endif
31#ifdef HAVE_SYS_PARAM_H
32#include <sys/param.h>
33#endif
34#ifdef HAVE_FCNTL_H
35#include <fcntl.h>
36#endif
37#ifdef HAVE_LIMITS_H
38#include <limits.h>
39#endif
40#ifdef HAVE_UNISTD_H
41#include <unistd.h>
42#endif
43#ifdef HAVE_LINUX_TYPES_H
44#include <linux/types.h>
45#endif
46#ifdef HAVE_LINUX_FIEMAP_H
47#include <linux/fiemap.h>
48#endif
49#ifdef HAVE_LINUX_FS_H
50#include <linux/fs.h>
51#endif
52
53/* The logic to compare sparse file data read from disk with the
54 * specification is a little involved.  Set to 1 to have the progress
55 * dumped. */
56#define DEBUG 0
57
58/*
59 * NOTE: On FreeBSD and Solaris, this test needs ZFS.
60 * You may should perfom this test as
61 * 'TMPDIR=<a directory on the ZFS> libarchive_test'.
62 */
63
64struct sparse {
65	enum { DATA, HOLE, END } type;
66	size_t	size;
67};
68
69static void create_sparse_file(const char *, const struct sparse *);
70
71#if defined(_WIN32) && !defined(__CYGWIN__)
72#include <winioctl.h>
73/*
74 * Create a sparse file on Windows.
75 */
76
77#if !defined(PATH_MAX)
78#define	PATH_MAX	MAX_PATH
79#endif
80#if !defined(__BORLANDC__)
81#define getcwd _getcwd
82#endif
83
84static int
85is_sparse_supported(const char *path)
86{
87	char root[MAX_PATH+1];
88	char vol[MAX_PATH+1];
89	char sys[MAX_PATH+1];
90	DWORD flags;
91	BOOL r;
92
93	strncpy(root, path, sizeof(root)-1);
94	if (((root[0] >= 'c' && root[0] <= 'z') ||
95	    (root[0] >= 'C' && root[0] <= 'Z')) &&
96		root[1] == ':' &&
97	    (root[2] == '\\' || root[2] == '/'))
98		root[3] = '\0';
99	else
100		return (0);
101	assertEqualInt((r = GetVolumeInformation(root, vol,
102	    sizeof(vol), NULL, NULL, &flags, sys, sizeof(sys))), 1);
103	return (r != 0 && (flags & FILE_SUPPORTS_SPARSE_FILES) != 0);
104}
105
106static void
107create_sparse_file(const char *path, const struct sparse *s)
108{
109	char buff[1024];
110	HANDLE handle;
111	DWORD dmy;
112
113	memset(buff, ' ', sizeof(buff));
114
115	handle = CreateFileA(path, GENERIC_WRITE, 0,
116	    NULL, CREATE_NEW, FILE_ATTRIBUTE_NORMAL,
117	    NULL);
118	assert(handle != INVALID_HANDLE_VALUE);
119	assert(DeviceIoControl(handle, FSCTL_SET_SPARSE, NULL, 0,
120	    NULL, 0, &dmy, NULL) != 0);
121	while (s->type != END) {
122		if (s->type == HOLE) {
123			LARGE_INTEGER distance;
124
125			distance.QuadPart = s->size;
126			assert(SetFilePointerEx(handle, distance,
127			    NULL, FILE_CURRENT) != 0);
128		} else {
129			DWORD w, wr;
130			size_t size;
131
132			size = s->size;
133			while (size) {
134				if (size > sizeof(buff))
135					w = sizeof(buff);
136				else
137					w = (DWORD)size;
138				assert(WriteFile(handle, buff, w, &wr, NULL) != 0);
139				size -= wr;
140			}
141		}
142		s++;
143	}
144	assertEqualInt(CloseHandle(handle), 1);
145}
146
147#else
148
149#if defined(_PC_MIN_HOLE_SIZE)
150
151/*
152 * FreeBSD and Solaris can detect 'hole' of a sparse file
153 * through lseek(HOLE) on ZFS. (UFS does not support yet)
154 */
155
156static int
157is_sparse_supported(const char *path)
158{
159	return (pathconf(path, _PC_MIN_HOLE_SIZE) > 0);
160}
161
162#elif defined(__linux__)&& defined(HAVE_LINUX_FIEMAP_H)
163
164/*
165 * FIEMAP, which can detect 'hole' of a sparse file, has
166 * been supported from 2.6.28
167 */
168
169static int
170is_sparse_supported(const char *path)
171{
172	const struct sparse sparse_file[] = {
173 		/* This hole size is too small to create a sparse
174		 * files for almost filesystem. */
175		{ HOLE,	 1024 }, { DATA, 10240 },
176		{ END,	0 }
177	};
178	int fd, r;
179	struct fiemap *fm;
180	char buff[1024];
181	const char *testfile = "can_sparse";
182
183	(void)path; /* UNUSED */
184	memset(buff, 0, sizeof(buff));
185	create_sparse_file(testfile, sparse_file);
186	fd = open(testfile,  O_RDWR);
187	if (fd < 0)
188		return (0);
189	fm = (struct fiemap *)buff;
190	fm->fm_start = 0;
191	fm->fm_length = ~0ULL;;
192	fm->fm_flags = FIEMAP_FLAG_SYNC;
193	fm->fm_extent_count = (sizeof(buff) - sizeof(*fm))/
194		sizeof(struct fiemap_extent);
195	r = ioctl(fd, FS_IOC_FIEMAP, fm);
196	close(fd);
197	unlink(testfile);
198	return (r >= 0);
199}
200
201#else
202
203/*
204 * Other system may do not have the API such as lseek(HOLE),
205 * which detect 'hole' of a sparse file.
206 */
207
208static int
209is_sparse_supported(const char *path)
210{
211	(void)path; /* UNUSED */
212	return (0);
213}
214
215#endif
216
217/*
218 * Create a sparse file on POSIX like system.
219 */
220
221static void
222create_sparse_file(const char *path, const struct sparse *s)
223{
224	char buff[1024];
225	int fd;
226	size_t total_size = 0;
227	const struct sparse *cur = s;
228
229	memset(buff, ' ', sizeof(buff));
230	assert((fd = open(path, O_CREAT | O_WRONLY, 0600)) != -1);
231
232	/* Handle holes at the end by extending the file */
233	while (cur->type != END) {
234		total_size += cur->size;
235		++cur;
236	}
237	assert(ftruncate(fd, total_size) != -1);
238
239	while (s->type != END) {
240		if (s->type == HOLE) {
241			assert(lseek(fd, s->size, SEEK_CUR) != (off_t)-1);
242		} else {
243			size_t w, size;
244
245			size = s->size;
246			while (size) {
247				if (size > sizeof(buff))
248					w = sizeof(buff);
249				else
250					w = size;
251				assert(write(fd, buff, w) != (ssize_t)-1);
252				size -= w;
253			}
254		}
255		s++;
256	}
257	close(fd);
258}
259
260#endif
261
262/*
263 * Sparse test with directory traversals.
264 */
265static void
266verify_sparse_file(struct archive *a, const char *path,
267    const struct sparse *sparse, int expected_holes)
268{
269	struct archive_entry *ae;
270	const void *buff;
271	size_t bytes_read;
272	int64_t offset, expected_offset, last_offset;
273	int holes_seen = 0;
274
275	create_sparse_file(path, sparse);
276	assert((ae = archive_entry_new()) != NULL);
277	assertEqualIntA(a, ARCHIVE_OK, archive_read_disk_open(a, path));
278	assertEqualIntA(a, ARCHIVE_OK, archive_read_next_header2(a, ae));
279
280	expected_offset = 0;
281	last_offset = 0;
282	while (ARCHIVE_OK == archive_read_data_block(a, &buff, &bytes_read,
283	    &offset)) {
284		const char *start = buff;
285#if DEBUG
286		fprintf(stderr, "%s: bytes_read=%d offset=%d\n", path, (int)bytes_read, (int)offset);
287#endif
288		if (offset > last_offset) {
289			++holes_seen;
290		}
291		/* Blocks entirely before the data we just read. */
292		while (expected_offset + (int64_t)sparse->size < offset) {
293#if DEBUG
294			fprintf(stderr, "    skipping expected_offset=%d, size=%d\n", (int)expected_offset, (int)sparse->size);
295#endif
296			/* Must be holes. */
297			assert(sparse->type == HOLE);
298			expected_offset += sparse->size;
299			++sparse;
300		}
301		/* Block that overlaps beginning of data */
302		if (expected_offset < offset
303		    && expected_offset + (int64_t)sparse->size <= offset + (int64_t)bytes_read) {
304			const char *end = (const char *)buff + (expected_offset - offset) + (size_t)sparse->size;
305#if DEBUG
306			fprintf(stderr, "    overlapping hole expected_offset=%d, size=%d\n", (int)expected_offset, (int)sparse->size);
307#endif
308			/* Must be a hole, overlap must be filled with '\0' */
309			if (assert(sparse->type == HOLE)) {
310				assertMemoryFilledWith(start, end - start, '\0');
311			}
312			start = end;
313			expected_offset += sparse->size;
314			++sparse;
315		}
316		/* Blocks completely contained in data we just read. */
317		while (expected_offset + (int64_t)sparse->size <= offset + (int64_t)bytes_read) {
318			const char *end = (const char *)buff + (expected_offset - offset) + (size_t)sparse->size;
319			if (sparse->type == HOLE) {
320#if DEBUG
321				fprintf(stderr, "    contained hole expected_offset=%d, size=%d\n", (int)expected_offset, (int)sparse->size);
322#endif
323
324				/* verify data corresponding to hole is '\0' */
325				if (end > (const char *)buff + bytes_read) {
326					end = (const char *)buff + bytes_read;
327				}
328				assertMemoryFilledWith(start, end - start, '\0');
329				start = end;
330				expected_offset += sparse->size;
331				++sparse;
332			} else if (sparse->type == DATA) {
333#if DEBUG
334				fprintf(stderr, "    contained data expected_offset=%d, size=%d\n", (int)expected_offset, (int)sparse->size);
335#endif
336				/* verify data corresponding to hole is ' ' */
337				if (assert(expected_offset + sparse->size <= offset + bytes_read)) {
338					assert(start == (const char *)buff + (size_t)(expected_offset - offset));
339					assertMemoryFilledWith(start, end - start, ' ');
340				}
341				start = end;
342				expected_offset += sparse->size;
343				++sparse;
344			} else {
345				break;
346			}
347		}
348		/* Block that overlaps end of data */
349		if (expected_offset < offset + (int64_t)bytes_read) {
350			const char *end = (const char *)buff + bytes_read;
351#if DEBUG
352			fprintf(stderr, "    trailing overlap expected_offset=%d, size=%d\n", (int)expected_offset, (int)sparse->size);
353#endif
354			/* Must be a hole, overlap must be filled with '\0' */
355			if (assert(sparse->type == HOLE)) {
356				assertMemoryFilledWith(start, end - start, '\0');
357			}
358		}
359		last_offset = offset + bytes_read;
360	}
361	/* Count a hole at EOF? */
362	if (last_offset < archive_entry_size(ae)) {
363		++holes_seen;
364	}
365
366	/* Verify blocks after last read */
367	while (sparse->type == HOLE) {
368		expected_offset += sparse->size;
369		++sparse;
370	}
371	assert(sparse->type == END);
372	assertEqualInt(expected_offset, archive_entry_size(ae));
373
374	assertEqualInt(holes_seen, expected_holes);
375
376	assertEqualIntA(a, ARCHIVE_OK, archive_read_close(a));
377	archive_entry_free(ae);
378}
379
380#if defined(_WIN32) && !defined(__CYGWIN__)
381#define	close		_close
382#define	open		_open
383#endif
384
385/*
386 * Sparse test without directory traversals.
387 */
388static void
389verify_sparse_file2(struct archive *a, const char *path,
390    const struct sparse *sparse, int blocks, int preopen)
391{
392	struct archive_entry *ae;
393	int fd;
394
395	(void)sparse; /* UNUSED */
396	assert((ae = archive_entry_new()) != NULL);
397	archive_entry_set_pathname(ae, path);
398	if (preopen)
399		fd = open(path, O_RDONLY | O_BINARY);
400	else
401		fd = -1;
402	assertEqualIntA(a, ARCHIVE_OK,
403	    archive_read_disk_entry_from_file(a, ae, fd, NULL));
404	if (fd >= 0)
405		close(fd);
406	/* Verify the number of holes only, not its offset nor its
407	 * length because those alignments are deeply dependence on
408	 * its filesystem. */
409	assertEqualInt(blocks, archive_entry_sparse_count(ae));
410	archive_entry_free(ae);
411}
412
413static void
414test_sparse_whole_file_data()
415{
416	struct archive_entry *ae;
417	int64_t offset;
418	int i;
419
420	assert((ae = archive_entry_new()) != NULL);
421	archive_entry_set_size(ae, 1024*10);
422
423	/*
424	 * Add sparse block data up to the file size.
425	 */
426	offset = 0;
427	for (i = 0; i < 10; i++) {
428		archive_entry_sparse_add_entry(ae, offset, 1024);
429		offset += 1024;
430	}
431
432	failure("There should be no sparse");
433	assertEqualInt(0, archive_entry_sparse_count(ae));
434	archive_entry_free(ae);
435}
436
437DEFINE_TEST(test_sparse_basic)
438{
439	char *cwd;
440	struct archive *a;
441	/*
442	 * The alignment of the hole of sparse files deeply depends
443	 * on filesystem. In my experience, sparse_file2 test with
444	 * 204800 bytes hole size did not pass on ZFS and the result
445	 * of that test seemed the size was too small, thus you should
446	 * keep a hole size more than 409600 bytes to pass this test
447	 * on all platform.
448	 */
449	const struct sparse sparse_file0[] = {
450		{ DATA,	 1024 }, { HOLE,   2048000 },
451		{ DATA,	 2048 }, { HOLE,   2048000 },
452		{ DATA,	 4096 }, { HOLE,  20480000 },
453		{ DATA,	 8192 }, { HOLE, 204800000 },
454		{ DATA,     1 }, { END,	0 }
455	};
456	const struct sparse sparse_file1[] = {
457		{ HOLE,	409600 }, { DATA, 1 },
458		{ HOLE,	409600 }, { DATA, 1 },
459		{ HOLE,	409600 }, { END,  0 }
460	};
461	const struct sparse sparse_file2[] = {
462		{ HOLE,	409600 * 1 }, { DATA, 1024 },
463		{ HOLE,	409600 * 2 }, { DATA, 1024 },
464		{ HOLE,	409600 * 3 }, { DATA, 1024 },
465		{ HOLE,	409600 * 4 }, { DATA, 1024 },
466		{ HOLE,	409600 * 5 }, { DATA, 1024 },
467		{ HOLE,	409600 * 6 }, { DATA, 1024 },
468		{ HOLE,	409600 * 7 }, { DATA, 1024 },
469		{ HOLE,	409600 * 8 }, { DATA, 1024 },
470		{ HOLE,	409600 * 9 }, { DATA, 1024 },
471		{ HOLE,	409600 * 10}, { DATA, 1024 },/* 10 */
472		{ HOLE,	409600 * 1 }, { DATA, 1024 * 1 },
473		{ HOLE,	409600 * 2 }, { DATA, 1024 * 2 },
474		{ HOLE,	409600 * 3 }, { DATA, 1024 * 3 },
475		{ HOLE,	409600 * 4 }, { DATA, 1024 * 4 },
476		{ HOLE,	409600 * 5 }, { DATA, 1024 * 5 },
477		{ HOLE,	409600 * 6 }, { DATA, 1024 * 6 },
478		{ HOLE,	409600 * 7 }, { DATA, 1024 * 7 },
479		{ HOLE,	409600 * 8 }, { DATA, 1024 * 8 },
480		{ HOLE,	409600 * 9 }, { DATA, 1024 * 9 },
481		{ HOLE,	409600 * 10}, { DATA, 1024 * 10},/* 20 */
482		{ END,	0 }
483	};
484	const struct sparse sparse_file3[] = {
485 		/* This hole size is too small to create a sparse file */
486		{ HOLE,	 1 }, { DATA, 10240 },
487		{ HOLE,	 1 }, { DATA, 10240 },
488		{ HOLE,	 1 }, { DATA, 10240 },
489		{ END,	0 }
490	};
491
492	/*
493	 * Test for the case that sparse data indicates just the whole file
494	 * data.
495	 */
496	test_sparse_whole_file_data();
497
498	/* Check if the filesystem where CWD on can
499	 * report the number of the holes of a sparse file. */
500#ifdef PATH_MAX
501	cwd = getcwd(NULL, PATH_MAX);/* Solaris getcwd needs the size. */
502#else
503	cwd = getcwd(NULL, 0);
504#endif
505	if (!assert(cwd != NULL))
506		return;
507	if (!is_sparse_supported(cwd)) {
508		free(cwd);
509		skipping("This filesystem or platform do not support "
510		    "the reporting of the holes of a sparse file through "
511		    "API such as lseek(HOLE)");
512		return;
513	}
514
515	/*
516	 * Get sparse data through directory traversals.
517	 */
518	assert((a = archive_read_disk_new()) != NULL);
519
520	verify_sparse_file(a, "file0", sparse_file0, 4);
521	verify_sparse_file(a, "file1", sparse_file1, 3);
522	verify_sparse_file(a, "file2", sparse_file2, 20);
523	/* Encoded non sparse; expect a data block but no sparse entries. */
524	verify_sparse_file(a, "file3", sparse_file3, 0);
525
526	assertEqualInt(ARCHIVE_OK, archive_read_free(a));
527
528	/*
529	 * Get sparse data through archive_read_disk_entry_from_file().
530	 */
531	assert((a = archive_read_disk_new()) != NULL);
532
533	verify_sparse_file2(a, "file0", sparse_file0, 5, 0);
534	verify_sparse_file2(a, "file0", sparse_file0, 5, 1);
535
536	assertEqualInt(ARCHIVE_OK, archive_read_free(a));
537	free(cwd);
538}
539
540DEFINE_TEST(test_fully_sparse_files)
541{
542	char *cwd;
543	struct archive *a;
544
545	const struct sparse sparse_file[] = {
546		{ HOLE, 409600 }, { END, 0 }
547	};
548	/* Check if the filesystem where CWD on can
549	 * report the number of the holes of a sparse file. */
550#ifdef PATH_MAX
551	cwd = getcwd(NULL, PATH_MAX);/* Solaris getcwd needs the size. */
552#else
553	cwd = getcwd(NULL, 0);
554#endif
555	if (!assert(cwd != NULL))
556		return;
557	if (!is_sparse_supported(cwd)) {
558		free(cwd);
559		skipping("This filesystem or platform do not support "
560		    "the reporting of the holes of a sparse file through "
561		    "API such as lseek(HOLE)");
562		return;
563	}
564
565	assert((a = archive_read_disk_new()) != NULL);
566
567	/* Fully sparse files are encoded with a zero-length "data" block. */
568	verify_sparse_file(a, "file0", sparse_file, 1);
569
570	assertEqualInt(ARCHIVE_OK, archive_read_free(a));
571	free(cwd);
572}
573