xref: /dragonfly/sys/vfs/hammer/hammer_reblock.c (revision 927da715)
1 /*
2  * Copyright (c) 2008 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  * $DragonFly: src/sys/vfs/hammer/hammer_reblock.c,v 1.33 2008/07/16 18:30:59 dillon Exp $
35  */
36 /*
37  * HAMMER reblocker - This code frees up fragmented physical space
38  *
39  * HAMMER only keeps track of free space on a big-block basis.  A big-block
40  * containing holes can only be freed by migrating the remaining data in
41  * that big-block into a new big-block, then freeing the big-block.
42  *
43  * This function is called from an ioctl or via the hammer support thread.
44  */
45 
46 #include "hammer.h"
47 
48 static int hammer_reblock_helper(struct hammer_ioc_reblock *reblock,
49 				 hammer_cursor_t cursor,
50 				 hammer_btree_elm_t elm);
51 static int hammer_reblock_data(struct hammer_ioc_reblock *reblock,
52 				hammer_cursor_t cursor, hammer_btree_elm_t elm);
53 static int hammer_reblock_leaf_node(struct hammer_ioc_reblock *reblock,
54 				hammer_cursor_t cursor, hammer_btree_elm_t elm);
55 static int hammer_reblock_int_node(struct hammer_ioc_reblock *reblock,
56 				hammer_cursor_t cursor, hammer_btree_elm_t elm);
57 
58 int
59 hammer_ioc_reblock(hammer_transaction_t trans, hammer_inode_t ip,
60 	       struct hammer_ioc_reblock *reblock)
61 {
62 	struct hammer_cursor cursor;
63 	hammer_btree_elm_t elm;
64 	int checkspace_count;
65 	int error;
66 	int seq;
67 	int slop;
68 
69 	/*
70 	 * A fill level <= 20% is considered an emergency.  free_level is
71 	 * inverted from fill_level.
72 	 */
73 	if (reblock->free_level >= HAMMER_LARGEBLOCK_SIZE * 8 / 10)
74 		slop = HAMMER_CHKSPC_EMERGENCY;
75 	else
76 		slop = HAMMER_CHKSPC_REBLOCK;
77 
78 	if ((reblock->key_beg.localization | reblock->key_end.localization) &
79 	    HAMMER_LOCALIZE_PSEUDOFS_MASK) {
80 		return(EINVAL);
81 	}
82 	if (reblock->key_beg.obj_id >= reblock->key_end.obj_id)
83 		return(EINVAL);
84 	if (reblock->free_level < 0)
85 		return(EINVAL);
86 
87 	reblock->key_cur = reblock->key_beg;
88 	reblock->key_cur.localization &= HAMMER_LOCALIZE_MASK;
89 	reblock->key_cur.localization += ip->obj_localization;
90 
91 	checkspace_count = 0;
92 	seq = trans->hmp->flusher.act;
93 retry:
94 	error = hammer_init_cursor(trans, &cursor, NULL, NULL);
95 	if (error) {
96 		hammer_done_cursor(&cursor);
97 		goto failed;
98 	}
99 	cursor.key_beg.localization = reblock->key_cur.localization;
100 	cursor.key_beg.obj_id = reblock->key_cur.obj_id;
101 	cursor.key_beg.key = HAMMER_MIN_KEY;
102 	cursor.key_beg.create_tid = 1;
103 	cursor.key_beg.delete_tid = 0;
104 	cursor.key_beg.rec_type = HAMMER_MIN_RECTYPE;
105 	cursor.key_beg.obj_type = 0;
106 
107 	cursor.key_end.localization = (reblock->key_end.localization &
108 					HAMMER_LOCALIZE_MASK) +
109 				      ip->obj_localization;
110 	cursor.key_end.obj_id = reblock->key_end.obj_id;
111 	cursor.key_end.key = HAMMER_MAX_KEY;
112 	cursor.key_end.create_tid = HAMMER_MAX_TID - 1;
113 	cursor.key_end.delete_tid = 0;
114 	cursor.key_end.rec_type = HAMMER_MAX_RECTYPE;
115 	cursor.key_end.obj_type = 0;
116 
117 	cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
118 	cursor.flags |= HAMMER_CURSOR_BACKEND;
119 
120 	/*
121 	 * This flag allows the btree scan code to return internal nodes,
122 	 * so we can reblock them in addition to the leafs.  Only specify it
123 	 * if we intend to reblock B-Tree nodes.
124 	 */
125 	if (reblock->head.flags & HAMMER_IOC_DO_BTREE)
126 		cursor.flags |= HAMMER_CURSOR_REBLOCKING;
127 
128 	error = hammer_btree_first(&cursor);
129 	while (error == 0) {
130 		/*
131 		 * Internal or Leaf node
132 		 */
133 		elm = &cursor.node->ondisk->elms[cursor.index];
134 		reblock->key_cur.obj_id = elm->base.obj_id;
135 		reblock->key_cur.localization = elm->base.localization;
136 
137 		/*
138 		 * Yield to more important tasks
139 		 */
140 		if ((error = hammer_signal_check(trans->hmp)) != 0)
141 			break;
142 
143 		/*
144 		 * If there is insufficient free space it may be due to
145 		 * reserved bigblocks, which flushing might fix.
146 		 */
147 		if (hammer_checkspace(trans->hmp, slop)) {
148 			if (++checkspace_count == 10) {
149 				error = ENOSPC;
150 				break;
151 			}
152 			hammer_unlock_cursor(&cursor, 0);
153 			hammer_flusher_wait(trans->hmp, seq);
154 			hammer_lock_cursor(&cursor, 0);
155 			seq = hammer_flusher_async(trans->hmp, NULL);
156 			continue;
157 		}
158 
159 		/*
160 		 * Acquiring the sync_lock prevents the operation from
161 		 * crossing a synchronization boundary.
162 		 *
163 		 * NOTE: cursor.node may have changed on return.
164 		 */
165 		hammer_sync_lock_sh(trans);
166 		error = hammer_reblock_helper(reblock, &cursor, elm);
167 		hammer_sync_unlock(trans);
168 
169 		while (hammer_flusher_meta_halflimit(trans->hmp) ||
170 		       hammer_flusher_undo_exhausted(trans, 2)) {
171 			hammer_unlock_cursor(&cursor, 0);
172 			hammer_flusher_wait(trans->hmp, seq);
173 			hammer_lock_cursor(&cursor, 0);
174 			seq = hammer_flusher_async_one(trans->hmp);
175 		}
176 
177 		/*
178 		 * Setup for iteration, our cursor flags may be modified by
179 		 * other threads while we are unlocked.
180 		 */
181 		cursor.flags |= HAMMER_CURSOR_ATEDISK;
182 
183 		/*
184 		 * We allocate data buffers, which atm we don't track
185 		 * dirty levels for because we allow the kernel to write
186 		 * them.  But if we allocate too many we can still deadlock
187 		 * the buffer cache.
188 		 *
189 		 * (The cursor's node and element may change!)
190 		 */
191 		if (bd_heatup()) {
192 			hammer_unlock_cursor(&cursor, 0);
193 			bwillwrite(HAMMER_XBUFSIZE);
194 			hammer_lock_cursor(&cursor, 0);
195 		}
196 
197 		if (error == 0) {
198 			error = hammer_btree_iterate(&cursor);
199 		}
200 
201 	}
202 	if (error == ENOENT)
203 		error = 0;
204 	hammer_done_cursor(&cursor);
205 	if (error == EWOULDBLOCK) {
206 		hammer_flusher_sync(trans->hmp);
207 		goto retry;
208 	}
209 	if (error == EDEADLK)
210 		goto retry;
211 	if (error == EINTR) {
212 		reblock->head.flags |= HAMMER_IOC_HEAD_INTR;
213 		error = 0;
214 	}
215 failed:
216 	reblock->key_cur.localization &= HAMMER_LOCALIZE_MASK;
217 	return(error);
218 }
219 
220 /*
221  * Reblock the B-Tree (leaf) node, record, and/or data if necessary.
222  *
223  * XXX We have no visibility into internal B-Tree nodes at the moment,
224  * only leaf nodes.
225  */
226 static int
227 hammer_reblock_helper(struct hammer_ioc_reblock *reblock,
228 		      hammer_cursor_t cursor, hammer_btree_elm_t elm)
229 {
230 	hammer_mount_t hmp;
231 	hammer_off_t tmp_offset;
232 	int error;
233 	int bytes;
234 	int cur;
235 	int iocflags;
236 
237 	error = 0;
238 	hmp = cursor->trans->hmp;
239 
240 	/*
241 	 * Reblock data.  Note that data embedded in a record is reblocked
242 	 * by the record reblock code.  Data processing only occurs at leaf
243 	 * nodes and for RECORD element types.
244 	 */
245 	if (cursor->node->ondisk->type != HAMMER_BTREE_TYPE_LEAF)
246 		goto skip;
247 	if (elm->leaf.base.btype != HAMMER_BTREE_TYPE_RECORD)
248 		return(0);
249 	tmp_offset = elm->leaf.data_offset;
250 	if (tmp_offset == 0)
251 		goto skip;
252 	if (error)
253 		goto skip;
254 
255 	/*
256 	 * NOTE: Localization restrictions may also have been set-up, we can't
257 	 * just set the match flags willy-nilly here.
258 	 */
259 	switch(elm->leaf.base.rec_type) {
260 	case HAMMER_RECTYPE_INODE:
261 		iocflags = HAMMER_IOC_DO_INODES;
262 		break;
263 	case HAMMER_RECTYPE_EXT:
264 	case HAMMER_RECTYPE_FIX:
265 	case HAMMER_RECTYPE_PFS:
266 	case HAMMER_RECTYPE_DIRENTRY:
267 		iocflags = HAMMER_IOC_DO_DIRS;
268 		break;
269 	case HAMMER_RECTYPE_DATA:
270 	case HAMMER_RECTYPE_DB:
271 		iocflags = HAMMER_IOC_DO_DATA;
272 		break;
273 	default:
274 		iocflags = 0;
275 		break;
276 	}
277 	if (reblock->head.flags & iocflags) {
278 		++reblock->data_count;
279 		reblock->data_byte_count += elm->leaf.data_len;
280 		bytes = hammer_blockmap_getfree(hmp, tmp_offset, &cur, &error);
281 		if (hammer_debug_general & 0x4000)
282 			kprintf("D %6d/%d\n", bytes, reblock->free_level);
283 		if (error == 0 && (cur == 0 || reblock->free_level == 0) &&
284 		    bytes >= reblock->free_level) {
285 			hammer_io_direct_uncache(hmp, &elm->leaf);
286 			error = hammer_cursor_upgrade(cursor);
287 			if (error == 0) {
288 				error = hammer_reblock_data(reblock,
289 							    cursor, elm);
290 			}
291 			if (error == 0) {
292 				++reblock->data_moves;
293 				reblock->data_byte_moves += elm->leaf.data_len;
294 			}
295 		}
296 	}
297 
298 skip:
299 	/*
300 	 * Reblock a B-Tree internal or leaf node.
301 	 */
302 	tmp_offset = cursor->node->node_offset;
303 	if (cursor->index == 0 &&
304 	    error == 0 && (reblock->head.flags & HAMMER_IOC_DO_BTREE)) {
305 		++reblock->btree_count;
306 		bytes = hammer_blockmap_getfree(hmp, tmp_offset, &cur, &error);
307 		if (hammer_debug_general & 0x4000)
308 			kprintf("B %6d/%d\n", bytes, reblock->free_level);
309 		if (error == 0 && (cur == 0 || reblock->free_level == 0) &&
310 		    bytes >= reblock->free_level) {
311 			error = hammer_cursor_upgrade(cursor);
312 			if (error == 0) {
313 				if (cursor->parent)
314 					elm = &cursor->parent->ondisk->elms[cursor->parent_index];
315 				else
316 					elm = NULL;
317 				switch(cursor->node->ondisk->type) {
318 				case HAMMER_BTREE_TYPE_LEAF:
319 					error = hammer_reblock_leaf_node(
320 							reblock, cursor, elm);
321 					break;
322 				case HAMMER_BTREE_TYPE_INTERNAL:
323 					error = hammer_reblock_int_node(
324 							reblock, cursor, elm);
325 					break;
326 				default:
327 					panic("Illegal B-Tree node type");
328 				}
329 			}
330 			if (error == 0) {
331 				++reblock->btree_moves;
332 			}
333 		}
334 	}
335 
336 	hammer_cursor_downgrade(cursor);
337 	return(error);
338 }
339 
340 /*
341  * Reblock a record's data.  Both the B-Tree element and record pointers
342  * to the data must be adjusted.
343  */
344 static int
345 hammer_reblock_data(struct hammer_ioc_reblock *reblock,
346 		    hammer_cursor_t cursor, hammer_btree_elm_t elm)
347 {
348 	struct hammer_buffer *data_buffer = NULL;
349 	hammer_off_t ndata_offset;
350 	int error;
351 	void *ndata;
352 
353 	error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA |
354 					     HAMMER_CURSOR_GET_LEAF);
355 	if (error)
356 		return (error);
357 	ndata = hammer_alloc_data(cursor->trans, elm->leaf.data_len,
358 				  elm->leaf.base.rec_type,
359 				  &ndata_offset, &data_buffer, &error);
360 	if (error)
361 		goto done;
362 
363 	/*
364 	 * Move the data
365 	 */
366 	hammer_modify_buffer(cursor->trans, data_buffer, NULL, 0);
367 	bcopy(cursor->data, ndata, elm->leaf.data_len);
368 	hammer_modify_buffer_done(data_buffer);
369 
370 	hammer_blockmap_free(cursor->trans,
371 			     elm->leaf.data_offset, elm->leaf.data_len);
372 
373 	hammer_modify_node(cursor->trans, cursor->node,
374 			   &elm->leaf.data_offset, sizeof(hammer_off_t));
375 	elm->leaf.data_offset = ndata_offset;
376 	hammer_modify_node_done(cursor->node);
377 
378 done:
379 	if (data_buffer)
380 		hammer_rel_buffer(data_buffer, 0);
381 	return (error);
382 }
383 
384 /*
385  * Reblock a B-Tree leaf node.  The parent must be adjusted to point to
386  * the new copy of the leaf node.
387  *
388  * elm is a pointer to the parent element pointing at cursor.node.
389  */
390 static int
391 hammer_reblock_leaf_node(struct hammer_ioc_reblock *reblock,
392 			 hammer_cursor_t cursor, hammer_btree_elm_t elm)
393 {
394 	hammer_node_t onode;
395 	hammer_node_t nnode;
396 	int error;
397 
398 	onode = cursor->node;
399 	nnode = hammer_alloc_btree(cursor->trans, &error);
400 
401 	if (nnode == NULL)
402 		return (error);
403 
404 	/*
405 	 * Move the node
406 	 */
407 	hammer_lock_ex(&nnode->lock);
408 	hammer_modify_node_noundo(cursor->trans, nnode);
409 	bcopy(onode->ondisk, nnode->ondisk, sizeof(*nnode->ondisk));
410 
411 	if (elm) {
412 		/*
413 		 * We are not the root of the B-Tree
414 		 */
415 		hammer_modify_node(cursor->trans, cursor->parent,
416 				   &elm->internal.subtree_offset,
417 				   sizeof(elm->internal.subtree_offset));
418 		elm->internal.subtree_offset = nnode->node_offset;
419 		hammer_modify_node_done(cursor->parent);
420 	} else {
421 		/*
422 		 * We are the root of the B-Tree
423 		 */
424                 hammer_volume_t volume;
425 
426                 volume = hammer_get_root_volume(cursor->trans->hmp, &error);
427                 KKASSERT(error == 0);
428 
429                 hammer_modify_volume_field(cursor->trans, volume,
430 					   vol0_btree_root);
431                 volume->ondisk->vol0_btree_root = nnode->node_offset;
432                 hammer_modify_volume_done(volume);
433                 hammer_rel_volume(volume, 0);
434         }
435 
436 	hammer_cursor_replaced_node(onode, nnode);
437 	hammer_delete_node(cursor->trans, onode);
438 
439 	if (hammer_debug_general & 0x4000) {
440 		kprintf("REBLOCK LNODE %016llx -> %016llx\n",
441 			onode->node_offset, nnode->node_offset);
442 	}
443 	hammer_modify_node_done(nnode);
444 	cursor->node = nnode;
445 
446 	hammer_unlock(&onode->lock);
447 	hammer_rel_node(onode);
448 
449 	return (error);
450 }
451 
452 /*
453  * Reblock a B-Tree internal node.  The parent must be adjusted to point to
454  * the new copy of the internal node, and the node's children's parent
455  * pointers must also be adjusted to point to the new copy.
456  *
457  * elm is a pointer to the parent element pointing at cursor.node.
458  */
459 static int
460 hammer_reblock_int_node(struct hammer_ioc_reblock *reblock,
461 			 hammer_cursor_t cursor, hammer_btree_elm_t elm)
462 {
463 	hammer_node_locklist_t locklist = NULL;
464 	hammer_node_t onode;
465 	hammer_node_t nnode;
466 	int error;
467 	int i;
468 
469 	error = hammer_btree_lock_children(cursor, &locklist);
470 	if (error)
471 		goto done;
472 
473 	onode = cursor->node;
474 	nnode = hammer_alloc_btree(cursor->trans, &error);
475 
476 	if (nnode == NULL)
477 		goto done;
478 
479 	/*
480 	 * Move the node.  Adjust the parent's pointer to us first.
481 	 */
482 	hammer_lock_ex(&nnode->lock);
483 	hammer_modify_node_noundo(cursor->trans, nnode);
484 	bcopy(onode->ondisk, nnode->ondisk, sizeof(*nnode->ondisk));
485 
486 	if (elm) {
487 		/*
488 		 * We are not the root of the B-Tree
489 		 */
490 		hammer_modify_node(cursor->trans, cursor->parent,
491 				   &elm->internal.subtree_offset,
492 				   sizeof(elm->internal.subtree_offset));
493 		elm->internal.subtree_offset = nnode->node_offset;
494 		hammer_modify_node_done(cursor->parent);
495 	} else {
496 		/*
497 		 * We are the root of the B-Tree
498 		 */
499                 hammer_volume_t volume;
500 
501                 volume = hammer_get_root_volume(cursor->trans->hmp, &error);
502                 KKASSERT(error == 0);
503 
504                 hammer_modify_volume_field(cursor->trans, volume,
505 					   vol0_btree_root);
506                 volume->ondisk->vol0_btree_root = nnode->node_offset;
507                 hammer_modify_volume_done(volume);
508                 hammer_rel_volume(volume, 0);
509         }
510 
511 	/*
512 	 * Now adjust our children's pointers to us.
513 	 */
514 	for (i = 0; i < nnode->ondisk->count; ++i) {
515 		elm = &nnode->ondisk->elms[i];
516 		error = btree_set_parent(cursor->trans, nnode, elm);
517 		if (error)
518 			panic("reblock internal node: fixup problem");
519 	}
520 
521 	/*
522 	 * Clean up.
523 	 *
524 	 * The new node replaces the current node in the cursor.  The cursor
525 	 * expects it to be locked so leave it locked.  Discard onode.
526 	 */
527 	hammer_cursor_replaced_node(onode, nnode);
528 	hammer_delete_node(cursor->trans, onode);
529 
530 	if (hammer_debug_general & 0x4000) {
531 		kprintf("REBLOCK INODE %016llx -> %016llx\n",
532 			onode->node_offset, nnode->node_offset);
533 	}
534 	hammer_modify_node_done(nnode);
535 	cursor->node = nnode;
536 
537 	hammer_unlock(&onode->lock);
538 	hammer_rel_node(onode);
539 
540 done:
541 	hammer_btree_unlock_children(&locklist);
542 	return (error);
543 }
544 
545