1 /*
2  * Copyright (C) 2013 Fusion IO.  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 
19 #include <linux/slab.h>
20 #include "btrfs-tests.h"
21 #include "../ctree.h"
22 #include "../free-space-cache.h"
23 
24 #define BITS_PER_BITMAP		(PAGE_CACHE_SIZE * 8)
25 static struct btrfs_block_group_cache *init_test_block_group(void)
26 {
27 	struct btrfs_block_group_cache *cache;
28 
29 	cache = kzalloc(sizeof(*cache), GFP_NOFS);
30 	if (!cache)
31 		return NULL;
32 	cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
33 					GFP_NOFS);
34 	if (!cache->free_space_ctl) {
35 		kfree(cache);
36 		return NULL;
37 	}
38 
39 	cache->key.objectid = 0;
40 	cache->key.offset = 1024 * 1024 * 1024;
41 	cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
42 	cache->sectorsize = 4096;
43 
44 	spin_lock_init(&cache->lock);
45 	INIT_LIST_HEAD(&cache->list);
46 	INIT_LIST_HEAD(&cache->cluster_list);
47 	INIT_LIST_HEAD(&cache->new_bg_list);
48 
49 	btrfs_init_free_space_ctl(cache);
50 
51 	return cache;
52 }
53 
54 /*
55  * This test just does basic sanity checking, making sure we can add an exten
56  * entry and remove space from either end and the middle, and make sure we can
57  * remove space that covers adjacent extent entries.
58  */
59 static int test_extents(struct btrfs_block_group_cache *cache)
60 {
61 	int ret = 0;
62 
63 	test_msg("Running extent only tests\n");
64 
65 	/* First just make sure we can remove an entire entry */
66 	ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
67 	if (ret) {
68 		test_msg("Error adding initial extents %d\n", ret);
69 		return ret;
70 	}
71 
72 	ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
73 	if (ret) {
74 		test_msg("Error removing extent %d\n", ret);
75 		return ret;
76 	}
77 
78 	if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
79 		test_msg("Full remove left some lingering space\n");
80 		return -1;
81 	}
82 
83 	/* Ok edge and middle cases now */
84 	ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
85 	if (ret) {
86 		test_msg("Error adding half extent %d\n", ret);
87 		return ret;
88 	}
89 
90 	ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 1 * 1024 * 1024);
91 	if (ret) {
92 		test_msg("Error removing tail end %d\n", ret);
93 		return ret;
94 	}
95 
96 	ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
97 	if (ret) {
98 		test_msg("Error removing front end %d\n", ret);
99 		return ret;
100 	}
101 
102 	ret = btrfs_remove_free_space(cache, 2 * 1024 * 1024, 4096);
103 	if (ret) {
104 		test_msg("Error removing middle peice %d\n", ret);
105 		return ret;
106 	}
107 
108 	if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
109 		test_msg("Still have space at the front\n");
110 		return -1;
111 	}
112 
113 	if (test_check_exists(cache, 2 * 1024 * 1024, 4096)) {
114 		test_msg("Still have space in the middle\n");
115 		return -1;
116 	}
117 
118 	if (test_check_exists(cache, 3 * 1024 * 1024, 1 * 1024 * 1024)) {
119 		test_msg("Still have space at the end\n");
120 		return -1;
121 	}
122 
123 	/* Cleanup */
124 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
125 
126 	return 0;
127 }
128 
129 static int test_bitmaps(struct btrfs_block_group_cache *cache)
130 {
131 	u64 next_bitmap_offset;
132 	int ret;
133 
134 	test_msg("Running bitmap only tests\n");
135 
136 	ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
137 	if (ret) {
138 		test_msg("Couldn't create a bitmap entry %d\n", ret);
139 		return ret;
140 	}
141 
142 	ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
143 	if (ret) {
144 		test_msg("Error removing bitmap full range %d\n", ret);
145 		return ret;
146 	}
147 
148 	if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
149 		test_msg("Left some space in bitmap\n");
150 		return -1;
151 	}
152 
153 	ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
154 	if (ret) {
155 		test_msg("Couldn't add to our bitmap entry %d\n", ret);
156 		return ret;
157 	}
158 
159 	ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 2 * 1024 * 1024);
160 	if (ret) {
161 		test_msg("Couldn't remove middle chunk %d\n", ret);
162 		return ret;
163 	}
164 
165 	/*
166 	 * The first bitmap we have starts at offset 0 so the next one is just
167 	 * at the end of the first bitmap.
168 	 */
169 	next_bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
170 
171 	/* Test a bit straddling two bitmaps */
172 	ret = test_add_free_space_entry(cache, next_bitmap_offset -
173 				   (2 * 1024 * 1024), 4 * 1024 * 1024, 1);
174 	if (ret) {
175 		test_msg("Couldn't add space that straddles two bitmaps %d\n",
176 				ret);
177 		return ret;
178 	}
179 
180 	ret = btrfs_remove_free_space(cache, next_bitmap_offset -
181 				      (1 * 1024 * 1024), 2 * 1024 * 1024);
182 	if (ret) {
183 		test_msg("Couldn't remove overlapping space %d\n", ret);
184 		return ret;
185 	}
186 
187 	if (test_check_exists(cache, next_bitmap_offset - (1 * 1024 * 1024),
188 			 2 * 1024 * 1024)) {
189 		test_msg("Left some space when removing overlapping\n");
190 		return -1;
191 	}
192 
193 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
194 
195 	return 0;
196 }
197 
198 /* This is the high grade jackassery */
199 static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache)
200 {
201 	u64 bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
202 	int ret;
203 
204 	test_msg("Running bitmap and extent tests\n");
205 
206 	/*
207 	 * First let's do something simple, an extent at the same offset as the
208 	 * bitmap, but the free space completely in the extent and then
209 	 * completely in the bitmap.
210 	 */
211 	ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 1 * 1024 * 1024, 1);
212 	if (ret) {
213 		test_msg("Couldn't create bitmap entry %d\n", ret);
214 		return ret;
215 	}
216 
217 	ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
218 	if (ret) {
219 		test_msg("Couldn't add extent entry %d\n", ret);
220 		return ret;
221 	}
222 
223 	ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
224 	if (ret) {
225 		test_msg("Couldn't remove extent entry %d\n", ret);
226 		return ret;
227 	}
228 
229 	if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
230 		test_msg("Left remnants after our remove\n");
231 		return -1;
232 	}
233 
234 	/* Now to add back the extent entry and remove from the bitmap */
235 	ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
236 	if (ret) {
237 		test_msg("Couldn't re-add extent entry %d\n", ret);
238 		return ret;
239 	}
240 
241 	ret = btrfs_remove_free_space(cache, 4 * 1024 * 1024, 1 * 1024 * 1024);
242 	if (ret) {
243 		test_msg("Couldn't remove from bitmap %d\n", ret);
244 		return ret;
245 	}
246 
247 	if (test_check_exists(cache, 4 * 1024 * 1024, 1 * 1024 * 1024)) {
248 		test_msg("Left remnants in the bitmap\n");
249 		return -1;
250 	}
251 
252 	/*
253 	 * Ok so a little more evil, extent entry and bitmap at the same offset,
254 	 * removing an overlapping chunk.
255 	 */
256 	ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 4 * 1024 * 1024, 1);
257 	if (ret) {
258 		test_msg("Couldn't add to a bitmap %d\n", ret);
259 		return ret;
260 	}
261 
262 	ret = btrfs_remove_free_space(cache, 512 * 1024, 3 * 1024 * 1024);
263 	if (ret) {
264 		test_msg("Couldn't remove overlapping space %d\n", ret);
265 		return ret;
266 	}
267 
268 	if (test_check_exists(cache, 512 * 1024, 3 * 1024 * 1024)) {
269 		test_msg("Left over peices after removing overlapping\n");
270 		return -1;
271 	}
272 
273 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
274 
275 	/* Now with the extent entry offset into the bitmap */
276 	ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 4 * 1024 * 1024, 1);
277 	if (ret) {
278 		test_msg("Couldn't add space to the bitmap %d\n", ret);
279 		return ret;
280 	}
281 
282 	ret = test_add_free_space_entry(cache, 2 * 1024 * 1024, 2 * 1024 * 1024, 0);
283 	if (ret) {
284 		test_msg("Couldn't add extent to the cache %d\n", ret);
285 		return ret;
286 	}
287 
288 	ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 4 * 1024 * 1024);
289 	if (ret) {
290 		test_msg("Problem removing overlapping space %d\n", ret);
291 		return ret;
292 	}
293 
294 	if (test_check_exists(cache, 3 * 1024 * 1024, 4 * 1024 * 1024)) {
295 		test_msg("Left something behind when removing space");
296 		return -1;
297 	}
298 
299 	/*
300 	 * This has blown up in the past, the extent entry starts before the
301 	 * bitmap entry, but we're trying to remove an offset that falls
302 	 * completely within the bitmap range and is in both the extent entry
303 	 * and the bitmap entry, looks like this
304 	 *
305 	 *   [ extent ]
306 	 *      [ bitmap ]
307 	 *        [ del ]
308 	 */
309 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
310 	ret = test_add_free_space_entry(cache, bitmap_offset + 4 * 1024 * 1024,
311 				   4 * 1024 * 1024, 1);
312 	if (ret) {
313 		test_msg("Couldn't add bitmap %d\n", ret);
314 		return ret;
315 	}
316 
317 	ret = test_add_free_space_entry(cache, bitmap_offset - 1 * 1024 * 1024,
318 				   5 * 1024 * 1024, 0);
319 	if (ret) {
320 		test_msg("Couldn't add extent entry %d\n", ret);
321 		return ret;
322 	}
323 
324 	ret = btrfs_remove_free_space(cache, bitmap_offset + 1 * 1024 * 1024,
325 				      5 * 1024 * 1024);
326 	if (ret) {
327 		test_msg("Failed to free our space %d\n", ret);
328 		return ret;
329 	}
330 
331 	if (test_check_exists(cache, bitmap_offset + 1 * 1024 * 1024,
332 			 5 * 1024 * 1024)) {
333 		test_msg("Left stuff over\n");
334 		return -1;
335 	}
336 
337 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
338 
339 	/*
340 	 * This blew up before, we have part of the free space in a bitmap and
341 	 * then the entirety of the rest of the space in an extent.  This used
342 	 * to return -EAGAIN back from btrfs_remove_extent, make sure this
343 	 * doesn't happen.
344 	 */
345 	ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 2 * 1024 * 1024, 1);
346 	if (ret) {
347 		test_msg("Couldn't add bitmap entry %d\n", ret);
348 		return ret;
349 	}
350 
351 	ret = test_add_free_space_entry(cache, 3 * 1024 * 1024, 1 * 1024 * 1024, 0);
352 	if (ret) {
353 		test_msg("Couldn't add extent entry %d\n", ret);
354 		return ret;
355 	}
356 
357 	ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 3 * 1024 * 1024);
358 	if (ret) {
359 		test_msg("Error removing bitmap and extent overlapping %d\n", ret);
360 		return ret;
361 	}
362 
363 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
364 	return 0;
365 }
366 
367 int btrfs_test_free_space_cache(void)
368 {
369 	struct btrfs_block_group_cache *cache;
370 	int ret;
371 
372 	test_msg("Running btrfs free space cache tests\n");
373 
374 	cache = init_test_block_group();
375 	if (!cache) {
376 		test_msg("Couldn't run the tests\n");
377 		return 0;
378 	}
379 
380 	ret = test_extents(cache);
381 	if (ret)
382 		goto out;
383 	ret = test_bitmaps(cache);
384 	if (ret)
385 		goto out;
386 	ret = test_bitmaps_and_extents(cache);
387 	if (ret)
388 		goto out;
389 out:
390 	__btrfs_remove_free_space_cache(cache->free_space_ctl);
391 	kfree(cache->free_space_ctl);
392 	kfree(cache);
393 	test_msg("Free space cache tests finished\n");
394 	return ret;
395 }
396