xref: /linux/fs/btrfs/zlib.c (revision 0d456bad36d42d16022be045c8a53ddbb59ee478)
1 /*
2  * Copyright (C) 2008 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  *
18  * Based on jffs2 zlib code:
19  * Copyright © 2001-2007 Red Hat, Inc.
20  * Created by David Woodhouse <dwmw2@infradead.org>
21  */
22 
23 #include <linux/kernel.h>
24 #include <linux/slab.h>
25 #include <linux/zlib.h>
26 #include <linux/zutil.h>
27 #include <linux/vmalloc.h>
28 #include <linux/init.h>
29 #include <linux/err.h>
30 #include <linux/sched.h>
31 #include <linux/pagemap.h>
32 #include <linux/bio.h>
33 #include "compression.h"
34 
35 struct workspace {
36 	z_stream inf_strm;
37 	z_stream def_strm;
38 	char *buf;
39 	struct list_head list;
40 };
41 
42 static void zlib_free_workspace(struct list_head *ws)
43 {
44 	struct workspace *workspace = list_entry(ws, struct workspace, list);
45 
46 	vfree(workspace->def_strm.workspace);
47 	vfree(workspace->inf_strm.workspace);
48 	kfree(workspace->buf);
49 	kfree(workspace);
50 }
51 
52 static struct list_head *zlib_alloc_workspace(void)
53 {
54 	struct workspace *workspace;
55 
56 	workspace = kzalloc(sizeof(*workspace), GFP_NOFS);
57 	if (!workspace)
58 		return ERR_PTR(-ENOMEM);
59 
60 	workspace->def_strm.workspace = vmalloc(zlib_deflate_workspacesize(
61 						MAX_WBITS, MAX_MEM_LEVEL));
62 	workspace->inf_strm.workspace = vmalloc(zlib_inflate_workspacesize());
63 	workspace->buf = kmalloc(PAGE_CACHE_SIZE, GFP_NOFS);
64 	if (!workspace->def_strm.workspace ||
65 	    !workspace->inf_strm.workspace || !workspace->buf)
66 		goto fail;
67 
68 	INIT_LIST_HEAD(&workspace->list);
69 
70 	return &workspace->list;
71 fail:
72 	zlib_free_workspace(&workspace->list);
73 	return ERR_PTR(-ENOMEM);
74 }
75 
76 static int zlib_compress_pages(struct list_head *ws,
77 			       struct address_space *mapping,
78 			       u64 start, unsigned long len,
79 			       struct page **pages,
80 			       unsigned long nr_dest_pages,
81 			       unsigned long *out_pages,
82 			       unsigned long *total_in,
83 			       unsigned long *total_out,
84 			       unsigned long max_out)
85 {
86 	struct workspace *workspace = list_entry(ws, struct workspace, list);
87 	int ret;
88 	char *data_in;
89 	char *cpage_out;
90 	int nr_pages = 0;
91 	struct page *in_page = NULL;
92 	struct page *out_page = NULL;
93 	unsigned long bytes_left;
94 
95 	*out_pages = 0;
96 	*total_out = 0;
97 	*total_in = 0;
98 
99 	if (Z_OK != zlib_deflateInit(&workspace->def_strm, 3)) {
100 		printk(KERN_WARNING "btrfs: deflateInit failed\n");
101 		ret = -1;
102 		goto out;
103 	}
104 
105 	workspace->def_strm.total_in = 0;
106 	workspace->def_strm.total_out = 0;
107 
108 	in_page = find_get_page(mapping, start >> PAGE_CACHE_SHIFT);
109 	data_in = kmap(in_page);
110 
111 	out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
112 	if (out_page == NULL) {
113 		ret = -1;
114 		goto out;
115 	}
116 	cpage_out = kmap(out_page);
117 	pages[0] = out_page;
118 	nr_pages = 1;
119 
120 	workspace->def_strm.next_in = data_in;
121 	workspace->def_strm.next_out = cpage_out;
122 	workspace->def_strm.avail_out = PAGE_CACHE_SIZE;
123 	workspace->def_strm.avail_in = min(len, PAGE_CACHE_SIZE);
124 
125 	while (workspace->def_strm.total_in < len) {
126 		ret = zlib_deflate(&workspace->def_strm, Z_SYNC_FLUSH);
127 		if (ret != Z_OK) {
128 			printk(KERN_DEBUG "btrfs: deflate in loop returned %d\n",
129 			       ret);
130 			zlib_deflateEnd(&workspace->def_strm);
131 			ret = -1;
132 			goto out;
133 		}
134 
135 		/* we're making it bigger, give up */
136 		if (workspace->def_strm.total_in > 8192 &&
137 		    workspace->def_strm.total_in <
138 		    workspace->def_strm.total_out) {
139 			ret = -1;
140 			goto out;
141 		}
142 		/* we need another page for writing out.  Test this
143 		 * before the total_in so we will pull in a new page for
144 		 * the stream end if required
145 		 */
146 		if (workspace->def_strm.avail_out == 0) {
147 			kunmap(out_page);
148 			if (nr_pages == nr_dest_pages) {
149 				out_page = NULL;
150 				ret = -1;
151 				goto out;
152 			}
153 			out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
154 			if (out_page == NULL) {
155 				ret = -1;
156 				goto out;
157 			}
158 			cpage_out = kmap(out_page);
159 			pages[nr_pages] = out_page;
160 			nr_pages++;
161 			workspace->def_strm.avail_out = PAGE_CACHE_SIZE;
162 			workspace->def_strm.next_out = cpage_out;
163 		}
164 		/* we're all done */
165 		if (workspace->def_strm.total_in >= len)
166 			break;
167 
168 		/* we've read in a full page, get a new one */
169 		if (workspace->def_strm.avail_in == 0) {
170 			if (workspace->def_strm.total_out > max_out)
171 				break;
172 
173 			bytes_left = len - workspace->def_strm.total_in;
174 			kunmap(in_page);
175 			page_cache_release(in_page);
176 
177 			start += PAGE_CACHE_SIZE;
178 			in_page = find_get_page(mapping,
179 						start >> PAGE_CACHE_SHIFT);
180 			data_in = kmap(in_page);
181 			workspace->def_strm.avail_in = min(bytes_left,
182 							   PAGE_CACHE_SIZE);
183 			workspace->def_strm.next_in = data_in;
184 		}
185 	}
186 	workspace->def_strm.avail_in = 0;
187 	ret = zlib_deflate(&workspace->def_strm, Z_FINISH);
188 	zlib_deflateEnd(&workspace->def_strm);
189 
190 	if (ret != Z_STREAM_END) {
191 		ret = -1;
192 		goto out;
193 	}
194 
195 	if (workspace->def_strm.total_out >= workspace->def_strm.total_in) {
196 		ret = -1;
197 		goto out;
198 	}
199 
200 	ret = 0;
201 	*total_out = workspace->def_strm.total_out;
202 	*total_in = workspace->def_strm.total_in;
203 out:
204 	*out_pages = nr_pages;
205 	if (out_page)
206 		kunmap(out_page);
207 
208 	if (in_page) {
209 		kunmap(in_page);
210 		page_cache_release(in_page);
211 	}
212 	return ret;
213 }
214 
215 static int zlib_decompress_biovec(struct list_head *ws, struct page **pages_in,
216 				  u64 disk_start,
217 				  struct bio_vec *bvec,
218 				  int vcnt,
219 				  size_t srclen)
220 {
221 	struct workspace *workspace = list_entry(ws, struct workspace, list);
222 	int ret = 0, ret2;
223 	int wbits = MAX_WBITS;
224 	char *data_in;
225 	size_t total_out = 0;
226 	unsigned long page_in_index = 0;
227 	unsigned long page_out_index = 0;
228 	unsigned long total_pages_in = (srclen + PAGE_CACHE_SIZE - 1) /
229 					PAGE_CACHE_SIZE;
230 	unsigned long buf_start;
231 	unsigned long pg_offset;
232 
233 	data_in = kmap(pages_in[page_in_index]);
234 	workspace->inf_strm.next_in = data_in;
235 	workspace->inf_strm.avail_in = min_t(size_t, srclen, PAGE_CACHE_SIZE);
236 	workspace->inf_strm.total_in = 0;
237 
238 	workspace->inf_strm.total_out = 0;
239 	workspace->inf_strm.next_out = workspace->buf;
240 	workspace->inf_strm.avail_out = PAGE_CACHE_SIZE;
241 	pg_offset = 0;
242 
243 	/* If it's deflate, and it's got no preset dictionary, then
244 	   we can tell zlib to skip the adler32 check. */
245 	if (srclen > 2 && !(data_in[1] & PRESET_DICT) &&
246 	    ((data_in[0] & 0x0f) == Z_DEFLATED) &&
247 	    !(((data_in[0]<<8) + data_in[1]) % 31)) {
248 
249 		wbits = -((data_in[0] >> 4) + 8);
250 		workspace->inf_strm.next_in += 2;
251 		workspace->inf_strm.avail_in -= 2;
252 	}
253 
254 	if (Z_OK != zlib_inflateInit2(&workspace->inf_strm, wbits)) {
255 		printk(KERN_WARNING "btrfs: inflateInit failed\n");
256 		return -1;
257 	}
258 	while (workspace->inf_strm.total_in < srclen) {
259 		ret = zlib_inflate(&workspace->inf_strm, Z_NO_FLUSH);
260 		if (ret != Z_OK && ret != Z_STREAM_END)
261 			break;
262 
263 		buf_start = total_out;
264 		total_out = workspace->inf_strm.total_out;
265 
266 		/* we didn't make progress in this inflate call, we're done */
267 		if (buf_start == total_out)
268 			break;
269 
270 		ret2 = btrfs_decompress_buf2page(workspace->buf, buf_start,
271 						 total_out, disk_start,
272 						 bvec, vcnt,
273 						 &page_out_index, &pg_offset);
274 		if (ret2 == 0) {
275 			ret = 0;
276 			goto done;
277 		}
278 
279 		workspace->inf_strm.next_out = workspace->buf;
280 		workspace->inf_strm.avail_out = PAGE_CACHE_SIZE;
281 
282 		if (workspace->inf_strm.avail_in == 0) {
283 			unsigned long tmp;
284 			kunmap(pages_in[page_in_index]);
285 			page_in_index++;
286 			if (page_in_index >= total_pages_in) {
287 				data_in = NULL;
288 				break;
289 			}
290 			data_in = kmap(pages_in[page_in_index]);
291 			workspace->inf_strm.next_in = data_in;
292 			tmp = srclen - workspace->inf_strm.total_in;
293 			workspace->inf_strm.avail_in = min(tmp,
294 							   PAGE_CACHE_SIZE);
295 		}
296 	}
297 	if (ret != Z_STREAM_END)
298 		ret = -1;
299 	else
300 		ret = 0;
301 done:
302 	zlib_inflateEnd(&workspace->inf_strm);
303 	if (data_in)
304 		kunmap(pages_in[page_in_index]);
305 	return ret;
306 }
307 
308 static int zlib_decompress(struct list_head *ws, unsigned char *data_in,
309 			   struct page *dest_page,
310 			   unsigned long start_byte,
311 			   size_t srclen, size_t destlen)
312 {
313 	struct workspace *workspace = list_entry(ws, struct workspace, list);
314 	int ret = 0;
315 	int wbits = MAX_WBITS;
316 	unsigned long bytes_left = destlen;
317 	unsigned long total_out = 0;
318 	char *kaddr;
319 
320 	workspace->inf_strm.next_in = data_in;
321 	workspace->inf_strm.avail_in = srclen;
322 	workspace->inf_strm.total_in = 0;
323 
324 	workspace->inf_strm.next_out = workspace->buf;
325 	workspace->inf_strm.avail_out = PAGE_CACHE_SIZE;
326 	workspace->inf_strm.total_out = 0;
327 	/* If it's deflate, and it's got no preset dictionary, then
328 	   we can tell zlib to skip the adler32 check. */
329 	if (srclen > 2 && !(data_in[1] & PRESET_DICT) &&
330 	    ((data_in[0] & 0x0f) == Z_DEFLATED) &&
331 	    !(((data_in[0]<<8) + data_in[1]) % 31)) {
332 
333 		wbits = -((data_in[0] >> 4) + 8);
334 		workspace->inf_strm.next_in += 2;
335 		workspace->inf_strm.avail_in -= 2;
336 	}
337 
338 	if (Z_OK != zlib_inflateInit2(&workspace->inf_strm, wbits)) {
339 		printk(KERN_WARNING "btrfs: inflateInit failed\n");
340 		return -1;
341 	}
342 
343 	while (bytes_left > 0) {
344 		unsigned long buf_start;
345 		unsigned long buf_offset;
346 		unsigned long bytes;
347 		unsigned long pg_offset = 0;
348 
349 		ret = zlib_inflate(&workspace->inf_strm, Z_NO_FLUSH);
350 		if (ret != Z_OK && ret != Z_STREAM_END)
351 			break;
352 
353 		buf_start = total_out;
354 		total_out = workspace->inf_strm.total_out;
355 
356 		if (total_out == buf_start) {
357 			ret = -1;
358 			break;
359 		}
360 
361 		if (total_out <= start_byte)
362 			goto next;
363 
364 		if (total_out > start_byte && buf_start < start_byte)
365 			buf_offset = start_byte - buf_start;
366 		else
367 			buf_offset = 0;
368 
369 		bytes = min(PAGE_CACHE_SIZE - pg_offset,
370 			    PAGE_CACHE_SIZE - buf_offset);
371 		bytes = min(bytes, bytes_left);
372 
373 		kaddr = kmap_atomic(dest_page);
374 		memcpy(kaddr + pg_offset, workspace->buf + buf_offset, bytes);
375 		kunmap_atomic(kaddr);
376 
377 		pg_offset += bytes;
378 		bytes_left -= bytes;
379 next:
380 		workspace->inf_strm.next_out = workspace->buf;
381 		workspace->inf_strm.avail_out = PAGE_CACHE_SIZE;
382 	}
383 
384 	if (ret != Z_STREAM_END && bytes_left != 0)
385 		ret = -1;
386 	else
387 		ret = 0;
388 
389 	zlib_inflateEnd(&workspace->inf_strm);
390 	return ret;
391 }
392 
393 struct btrfs_compress_op btrfs_zlib_compress = {
394 	.alloc_workspace	= zlib_alloc_workspace,
395 	.free_workspace		= zlib_free_workspace,
396 	.compress_pages		= zlib_compress_pages,
397 	.decompress_biovec	= zlib_decompress_biovec,
398 	.decompress		= zlib_decompress,
399 };
400