HAMMER 38C/Many: Undo/Synchronization and crash recovery
[dragonfly.git] / sys / vfs / hammer / hammer_reblock.c
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.7 2008/04/25 21:49:49 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_record(struct hammer_ioc_reblock *reblock,
54                                 hammer_cursor_t cursor, hammer_btree_elm_t elm);
55 static int hammer_reblock_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 error;
65
66         if (reblock->beg_obj_id >= reblock->end_obj_id)
67                 return(EINVAL);
68         if (reblock->free_level < 0)
69                 return(EINVAL);
70
71 retry:
72         error = hammer_init_cursor(trans, &cursor, NULL);
73         if (error) {
74                 hammer_done_cursor(&cursor);
75                 return(error);
76         }
77         cursor.key_beg.obj_id = reblock->cur_obj_id;
78         cursor.key_beg.key = HAMMER_MIN_KEY;
79         cursor.key_beg.create_tid = 1;
80         cursor.key_beg.delete_tid = 0;
81         cursor.key_beg.rec_type = HAMMER_MIN_RECTYPE;
82         cursor.key_beg.obj_type = 0;
83
84         cursor.key_end.obj_id = reblock->end_obj_id;
85         cursor.key_end.key = HAMMER_MAX_KEY;
86         cursor.key_end.create_tid = HAMMER_MAX_TID - 1;
87         cursor.key_end.delete_tid = 0;
88         cursor.key_end.rec_type = HAMMER_MAX_RECTYPE;
89         cursor.key_end.obj_type = 0;
90
91         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
92
93         error = hammer_btree_first(&cursor);
94         while (error == 0) {
95                 elm = &cursor.node->ondisk->elms[cursor.index];
96                 reblock->cur_obj_id = elm->base.obj_id;
97
98                 error = hammer_reblock_helper(reblock, &cursor, elm);
99                 if (error == 0) {
100                         cursor.flags |= HAMMER_CURSOR_ATEDISK;
101                         error = hammer_btree_iterate(&cursor);
102                 }
103                 if (error == 0)
104                         error = hammer_signal_check(trans->hmp);
105         }
106         if (error == ENOENT)
107                 error = 0;
108         hammer_done_cursor(&cursor);
109         if (error == EDEADLK)
110                 goto retry;
111         return(error);
112 }
113
114 /*
115  * Reblock the B-Tree (leaf) node, record, and/or data if necessary.
116  *
117  * XXX We have no visibility into internal B-Tree nodes at the moment.
118  */
119 static int
120 hammer_reblock_helper(struct hammer_ioc_reblock *reblock,
121                       hammer_cursor_t cursor, hammer_btree_elm_t elm)
122 {
123         hammer_off_t tmp_offset;
124         int error;
125         int zone;
126         int bytes;
127         int cur;
128
129         if (elm->leaf.base.btype != HAMMER_BTREE_TYPE_RECORD)
130                 return(0);
131         error = 0;
132
133         /*
134          * Reblock data.  Note that data embedded in a record is reblocked
135          * by the record reblock code.
136          */
137         tmp_offset = elm->leaf.data_offset;
138         zone = HAMMER_ZONE_DECODE(tmp_offset);          /* can be 0 */
139         if ((zone == HAMMER_ZONE_SMALL_DATA_INDEX ||
140              zone == HAMMER_ZONE_LARGE_DATA_INDEX) && error == 0) {
141                 ++reblock->data_count;
142                 reblock->data_byte_count += elm->leaf.data_len;
143                 bytes = hammer_blockmap_getfree(cursor->trans->hmp, tmp_offset,
144                                                 &cur, &error);
145                 if (error == 0 && cur == 0 && bytes > reblock->free_level) {
146                         if (hammer_debug_general & 0x4000)
147                                 kprintf("%6d ", bytes);
148                         error = hammer_cursor_upgrade(cursor);
149                         if (error == 0) {
150                                 error = hammer_reblock_data(reblock,
151                                                             cursor, elm);
152                         }
153                         if (error == 0) {
154                                 ++reblock->data_moves;
155                                 reblock->data_byte_moves += elm->leaf.data_len;
156                         }
157                 }
158         }
159
160         /*
161          * Reblock a record
162          */
163         tmp_offset = elm->leaf.rec_offset;
164         zone = HAMMER_ZONE_DECODE(tmp_offset);
165         if (zone == HAMMER_ZONE_RECORD_INDEX && error == 0) {
166                 ++reblock->record_count;
167                 bytes = hammer_blockmap_getfree(cursor->trans->hmp, tmp_offset,
168                                                 &cur, &error);
169                 if (error == 0 && cur == 0 && bytes > reblock->free_level) {
170                         if (hammer_debug_general & 0x4000)
171                                 kprintf("%6d ", bytes);
172                         error = hammer_cursor_upgrade(cursor);
173                         if (error == 0) {
174                                 error = hammer_reblock_record(reblock,
175                                                               cursor, elm);
176                         }
177                         if (error == 0) {
178                                 ++reblock->record_moves;
179                         }
180                 }
181         }
182
183         /*
184          * Reblock a B-Tree node.  Adjust elm to point at the parent's
185          * leaf entry.
186          */
187         tmp_offset = cursor->node->node_offset;
188         zone = HAMMER_ZONE_DECODE(tmp_offset);
189         if (zone == HAMMER_ZONE_BTREE_INDEX && error == 0 &&
190             cursor->index == 0) {
191                 ++reblock->btree_count;
192                 bytes = hammer_blockmap_getfree(cursor->trans->hmp, tmp_offset,
193                                                 &cur, &error);
194                 if (error == 0 && cur == 0 && bytes > reblock->free_level) {
195                         if (hammer_debug_general & 0x4000)
196                                 kprintf("%6d ", bytes);
197                         error = hammer_cursor_upgrade(cursor);
198                         if (error == 0) {
199                                 if (cursor->parent)
200                                         elm = &cursor->parent->ondisk->elms[cursor->parent_index];
201                                 else
202                                         elm = NULL;
203                                 error = hammer_reblock_node(reblock,
204                                                             cursor, elm);
205                         }
206                         if (error == 0) {
207                                 ++reblock->btree_moves;
208                         }
209                 }
210         }
211
212         hammer_cursor_downgrade(cursor);
213         return(error);
214 }
215
216 /*
217  * Reblock a record's data.  Both the B-Tree element and record pointers
218  * to the data must be adjusted.
219  */
220 static int
221 hammer_reblock_data(struct hammer_ioc_reblock *reblock,
222                     hammer_cursor_t cursor, hammer_btree_elm_t elm)
223 {
224         struct hammer_buffer *data_buffer = NULL;
225         hammer_off_t ndata_offset;
226         int error;
227         void *ndata;
228
229         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA |
230                                              HAMMER_CURSOR_GET_RECORD);
231         if (error)
232                 return (error);
233         ndata = hammer_alloc_data(cursor->trans, elm->leaf.data_len,
234                                   &ndata_offset, &data_buffer, &error);
235         if (error)
236                 goto done;
237
238         /*
239          * Move the data
240          */
241         hammer_modify_buffer(cursor->trans, data_buffer, NULL, 0);
242         bcopy(cursor->data, ndata, elm->leaf.data_len);
243         hammer_modify_buffer_done(data_buffer);
244
245         hammer_blockmap_free(cursor->trans,
246                              elm->leaf.data_offset, elm->leaf.data_len);
247
248         hammer_modify_record(cursor->trans, cursor->record_buffer,
249                              &cursor->record->base.data_off,
250                              sizeof(hammer_off_t));
251         cursor->record->base.data_off = ndata_offset;
252         hammer_modify_record_done(cursor->record_buffer);
253
254         hammer_modify_node(cursor->trans, cursor->node,
255                            &elm->leaf.data_offset, sizeof(hammer_off_t));
256         elm->leaf.data_offset = ndata_offset;
257         hammer_modify_node_done(cursor->node);
258
259 done:
260         if (data_buffer)
261                 hammer_rel_buffer(data_buffer, 0);
262         return (error);
263 }
264
265 /*
266  * Reblock a record.  The B-Tree must be adjusted to point to the new record
267  * and the existing record must be physically destroyed so a FS rebuild
268  * does not see two versions of the same record.
269  */
270 static int
271 hammer_reblock_record(struct hammer_ioc_reblock *reblock,
272                       hammer_cursor_t cursor, hammer_btree_elm_t elm)
273 {
274         struct hammer_buffer *rec_buffer = NULL;
275         hammer_off_t nrec_offset;
276         hammer_off_t ndata_offset;
277         hammer_record_ondisk_t orec;
278         hammer_record_ondisk_t nrec;
279         int error;
280         int inline_data;
281
282         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
283         if (error)
284                 return (error);
285
286         nrec = hammer_alloc_record(cursor->trans, &nrec_offset,
287                                    elm->leaf.base.rec_type, &rec_buffer,
288                                    0, NULL, NULL, &error);
289         if (error)
290                 goto done;
291
292         /*
293          * Move the record.  Check for an inline data reference and move that
294          * too if necessary.
295          */
296         orec = cursor->record;
297         hammer_modify_buffer(cursor->trans, rec_buffer, NULL, 0);
298         bcopy(orec, nrec, sizeof(*nrec));
299
300         if ((orec->base.data_off & HAMMER_OFF_ZONE_MASK) == HAMMER_ZONE_RECORD) {
301                 ndata_offset = orec->base.data_off - elm->leaf.rec_offset;
302                 KKASSERT(ndata_offset < sizeof(*nrec));
303                 ndata_offset += nrec_offset;
304                 inline_data = 1;
305         } else {
306                 ndata_offset = 0;
307                 inline_data = 0;
308         }
309
310         hammer_modify_record(cursor->trans, cursor->record_buffer,
311                              &orec->base.base.rec_type,
312                              sizeof(orec->base.base.rec_type));
313         orec->base.base.rec_type |= HAMMER_RECTYPE_MOVED;
314         hammer_modify_record_done(cursor->record_buffer);
315
316         hammer_blockmap_free(cursor->trans,
317                              elm->leaf.rec_offset, sizeof(*nrec));
318
319         if (hammer_debug_general & 0x4000) {
320                 kprintf("REBLOCK RECD %016llx -> %016llx\n",
321                         elm->leaf.rec_offset, nrec_offset);
322         }
323
324         hammer_modify_node(cursor->trans, cursor->node,
325                            &elm->leaf.rec_offset, sizeof(hammer_off_t));
326         elm->leaf.rec_offset = nrec_offset;
327         hammer_modify_node_done(cursor->node);
328         if (inline_data) {
329                 hammer_modify_node(cursor->trans, cursor->node,
330                                  &elm->leaf.data_offset, sizeof(hammer_off_t));
331                 elm->leaf.data_offset = ndata_offset;
332                 hammer_modify_node_done(cursor->node);
333                 nrec->base.data_off = ndata_offset;
334         }
335         hammer_modify_buffer_done(rec_buffer);
336
337 done:
338         if (rec_buffer)
339                 hammer_rel_buffer(rec_buffer, 0);
340         return (error);
341 }
342
343 /*
344  * Reblock a B-Tree (leaf) node.  The parent must be adjusted to point to
345  * the new copy of the leaf node.  elm is a pointer to the parent element
346  * pointing at cursor.node.
347  *
348  * XXX reblock internal nodes too.
349  */
350 static int
351 hammer_reblock_node(struct hammer_ioc_reblock *reblock,
352                     hammer_cursor_t cursor, hammer_btree_elm_t elm)
353 {
354         hammer_node_t onode;
355         hammer_node_t nnode;
356         int error;
357
358         onode = cursor->node;
359         nnode = hammer_alloc_btree(cursor->trans, &error);
360         hammer_lock_ex(&nnode->lock);
361
362         if (nnode == NULL)
363                 return (error);
364
365         /*
366          * Move the node
367          */
368         bcopy(onode->ondisk, nnode->ondisk, sizeof(*nnode->ondisk));
369
370         if (elm) {
371                 /*
372                  * We are not the root of the B-Tree 
373                  */
374                 hammer_modify_node(cursor->trans, cursor->parent,
375                                    &elm->internal.subtree_offset,
376                                    sizeof(elm->internal.subtree_offset));
377                 elm->internal.subtree_offset = nnode->node_offset;
378                 hammer_modify_node_done(cursor->parent);
379         } else {
380                 /*
381                  * We are the root of the B-Tree
382                  */
383                 hammer_volume_t volume;
384                         
385                 volume = hammer_get_root_volume(cursor->trans->hmp, &error);
386                 KKASSERT(error == 0);
387
388                 hammer_modify_volume(cursor->trans, volume,
389                                      &volume->ondisk->vol0_btree_root,
390                                      sizeof(hammer_off_t));
391                 volume->ondisk->vol0_btree_root = nnode->node_offset;
392                 hammer_modify_volume_done(volume);
393                 hammer_rel_volume(volume, 0);
394         }
395
396         hammer_delete_node(cursor->trans, onode);
397
398         if (hammer_debug_general & 0x4000) {
399                 kprintf("REBLOCK NODE %016llx -> %016llx\n",
400                         onode->node_offset, nnode->node_offset);
401         }
402
403         cursor->node = nnode;
404         hammer_rel_node(onode);
405
406         return (error);
407 }
408