Merge branch 'net80211-update' of git://leaf.dragonflybsd.org/~rpaulo/dragonfly into...
[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.34 2008/11/13 02:18:43 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                  * WARNING: See warnings in hammer_unlock_cursor() function.
148                  */
149                 if (hammer_checkspace(trans->hmp, slop)) {
150                         if (++checkspace_count == 10) {
151                                 error = ENOSPC;
152                                 break;
153                         }
154                         hammer_unlock_cursor(&cursor);
155                         hammer_flusher_wait(trans->hmp, seq);
156                         hammer_lock_cursor(&cursor);
157                         seq = hammer_flusher_async(trans->hmp, NULL);
158                         continue;
159                 }
160
161                 /*
162                  * Acquiring the sync_lock prevents the operation from
163                  * crossing a synchronization boundary.
164                  *
165                  * NOTE: cursor.node may have changed on return.
166                  *
167                  * WARNING: See warnings in hammer_unlock_cursor() function.
168                  */
169                 hammer_sync_lock_sh(trans);
170                 error = hammer_reblock_helper(reblock, &cursor, elm);
171                 hammer_sync_unlock(trans);
172
173                 while (hammer_flusher_meta_halflimit(trans->hmp) ||
174                        hammer_flusher_undo_exhausted(trans, 2)) {
175                         hammer_unlock_cursor(&cursor);
176                         hammer_flusher_wait(trans->hmp, seq);
177                         hammer_lock_cursor(&cursor);
178                         seq = hammer_flusher_async_one(trans->hmp);
179                 }
180
181                 /*
182                  * Setup for iteration, our cursor flags may be modified by
183                  * other threads while we are unlocked.
184                  */
185                 cursor.flags |= HAMMER_CURSOR_ATEDISK;
186
187                 /*
188                  * We allocate data buffers, which atm we don't track
189                  * dirty levels for because we allow the kernel to write
190                  * them.  But if we allocate too many we can still deadlock
191                  * the buffer cache.
192                  *
193                  * WARNING: See warnings in hammer_unlock_cursor() function.
194                  *          (The cursor's node and element may change!)
195                  */
196                 if (bd_heatup()) {
197                         hammer_unlock_cursor(&cursor);
198                         bwillwrite(HAMMER_XBUFSIZE);
199                         hammer_lock_cursor(&cursor);
200                 }
201
202                 if (error == 0) {
203                         error = hammer_btree_iterate(&cursor);
204                 }
205
206         }
207         if (error == ENOENT)
208                 error = 0;
209         hammer_done_cursor(&cursor);
210         if (error == EWOULDBLOCK) {
211                 hammer_flusher_sync(trans->hmp);
212                 goto retry;
213         }
214         if (error == EDEADLK)
215                 goto retry;
216         if (error == EINTR) {
217                 reblock->head.flags |= HAMMER_IOC_HEAD_INTR;
218                 error = 0;
219         }
220 failed:
221         reblock->key_cur.localization &= HAMMER_LOCALIZE_MASK;
222         return(error);
223 }
224
225 /*
226  * Reblock the B-Tree (leaf) node, record, and/or data if necessary.
227  *
228  * XXX We have no visibility into internal B-Tree nodes at the moment,
229  * only leaf nodes.
230  */
231 static int
232 hammer_reblock_helper(struct hammer_ioc_reblock *reblock,
233                       hammer_cursor_t cursor, hammer_btree_elm_t elm)
234 {
235         hammer_mount_t hmp;
236         hammer_off_t tmp_offset;
237         hammer_node_ondisk_t ondisk;
238         struct hammer_btree_leaf_elm leaf;
239         int error;
240         int bytes;
241         int cur;
242         int iocflags;
243
244         error = 0;
245         hmp = cursor->trans->hmp;
246
247         /*
248          * Reblock data.  Note that data embedded in a record is reblocked
249          * by the record reblock code.  Data processing only occurs at leaf
250          * nodes and for RECORD element types.
251          */
252         if (cursor->node->ondisk->type != HAMMER_BTREE_TYPE_LEAF)
253                 goto skip;
254         if (elm->leaf.base.btype != HAMMER_BTREE_TYPE_RECORD)
255                 return(0);
256         tmp_offset = elm->leaf.data_offset;
257         if (tmp_offset == 0)
258                 goto skip;
259         if (error)
260                 goto skip;
261
262         /*
263          * NOTE: Localization restrictions may also have been set-up, we can't
264          *       just set the match flags willy-nilly here.
265          */
266         switch(elm->leaf.base.rec_type) {
267         case HAMMER_RECTYPE_INODE:
268         case HAMMER_RECTYPE_SNAPSHOT:
269         case HAMMER_RECTYPE_CONFIG:
270                 iocflags = HAMMER_IOC_DO_INODES;
271                 break;
272         case HAMMER_RECTYPE_EXT:
273         case HAMMER_RECTYPE_FIX:
274         case HAMMER_RECTYPE_PFS:
275         case HAMMER_RECTYPE_DIRENTRY:
276                 iocflags = HAMMER_IOC_DO_DIRS;
277                 break;
278         case HAMMER_RECTYPE_DATA:
279         case HAMMER_RECTYPE_DB:
280                 iocflags = HAMMER_IOC_DO_DATA;
281                 break;
282         default:
283                 iocflags = 0;
284                 break;
285         }
286         if (reblock->head.flags & iocflags) {
287                 ++reblock->data_count;
288                 reblock->data_byte_count += elm->leaf.data_len;
289                 bytes = hammer_blockmap_getfree(hmp, tmp_offset, &cur, &error);
290                 if (hammer_debug_general & 0x4000)
291                         kprintf("D %6d/%d\n", bytes, reblock->free_level);
292                 if (error == 0 && (cur == 0 || reblock->free_level == 0) &&
293                     bytes >= reblock->free_level) {
294                         /*
295                          * This is nasty, the uncache code may have to get
296                          * vnode locks and because of that we can't hold
297                          * the cursor locked.
298                          *
299                          * WARNING: See warnings in hammer_unlock_cursor()
300                          *          function.
301                          */
302                         leaf = elm->leaf;
303                         hammer_unlock_cursor(cursor);
304                         hammer_io_direct_uncache(hmp, &leaf);
305                         hammer_lock_cursor(cursor);
306
307                         /*
308                          * elm may have become stale or invalid, reload it.
309                          * ondisk variable is temporary only.  Note that
310                          * cursor->node and thus cursor->node->ondisk may
311                          * also changed.
312                          */
313                         ondisk = cursor->node->ondisk;
314                         elm = &ondisk->elms[cursor->index];
315                         if (cursor->flags & HAMMER_CURSOR_RETEST) {
316                                 kprintf("hammer: debug: retest on "
317                                         "reblocker uncache\n");
318                                 error = EDEADLK;
319                         } else if (ondisk->type != HAMMER_BTREE_TYPE_LEAF ||
320                                    cursor->index >= ondisk->count) {
321                                 kprintf("hammer: debug: shifted on "
322                                         "reblocker uncache\n");
323                                 error = EDEADLK;
324                         } else if (bcmp(&elm->leaf, &leaf, sizeof(leaf))) {
325                                 kprintf("hammer: debug: changed on "
326                                         "reblocker uncache\n");
327                                 error = EDEADLK;
328                         }
329                         if (error == 0)
330                                 error = hammer_cursor_upgrade(cursor);
331                         if (error == 0) {
332                                 error = hammer_reblock_data(reblock,
333                                                             cursor, elm);
334                         }
335                         if (error == 0) {
336                                 ++reblock->data_moves;
337                                 reblock->data_byte_moves += elm->leaf.data_len;
338                         }
339                 }
340         }
341
342 skip:
343         /*
344          * Reblock a B-Tree internal or leaf node.  A leaf node is reblocked
345          * on initial entry only (element 0).  An internal node is reblocked
346          * when entered upward from its first leaf node only (also element 0).
347          * Further revisits of the internal node (index > 0) are ignored.
348          */
349         tmp_offset = cursor->node->node_offset;
350         if (cursor->index == 0 &&
351             error == 0 && (reblock->head.flags & HAMMER_IOC_DO_BTREE)) {
352                 ++reblock->btree_count;
353                 bytes = hammer_blockmap_getfree(hmp, tmp_offset, &cur, &error);
354                 if (hammer_debug_general & 0x4000)
355                         kprintf("B %6d/%d\n", bytes, reblock->free_level);
356                 if (error == 0 && (cur == 0 || reblock->free_level == 0) &&
357                     bytes >= reblock->free_level) {
358                         error = hammer_cursor_upgrade(cursor);
359                         if (error == 0) {
360                                 if (cursor->parent)
361                                         elm = &cursor->parent->ondisk->elms[cursor->parent_index];
362                                 else
363                                         elm = NULL;
364                                 switch(cursor->node->ondisk->type) {
365                                 case HAMMER_BTREE_TYPE_LEAF:
366                                         error = hammer_reblock_leaf_node(
367                                                         reblock, cursor, elm);
368                                         break;
369                                 case HAMMER_BTREE_TYPE_INTERNAL:
370                                         error = hammer_reblock_int_node(
371                                                         reblock, cursor, elm);
372                                         break;
373                                 default:
374                                         panic("Illegal B-Tree node type");
375                                 }
376                         }
377                         if (error == 0) {
378                                 ++reblock->btree_moves;
379                         }
380                 }
381         }
382
383         hammer_cursor_downgrade(cursor);
384         return(error);
385 }
386
387 /*
388  * Reblock a record's data.  Both the B-Tree element and record pointers
389  * to the data must be adjusted.
390  */
391 static int
392 hammer_reblock_data(struct hammer_ioc_reblock *reblock,
393                     hammer_cursor_t cursor, hammer_btree_elm_t elm)
394 {
395         struct hammer_buffer *data_buffer = NULL;
396         hammer_off_t ndata_offset;
397         int error;
398         void *ndata;
399
400         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA |
401                                              HAMMER_CURSOR_GET_LEAF);
402         if (error)
403                 return (error);
404         ndata = hammer_alloc_data(cursor->trans, elm->leaf.data_len,
405                                   elm->leaf.base.rec_type,
406                                   &ndata_offset, &data_buffer,
407                                   0, &error);
408         if (error)
409                 goto done;
410         hammer_io_notmeta(data_buffer);
411
412         /*
413          * Move the data
414          */
415         hammer_modify_buffer(cursor->trans, data_buffer, NULL, 0);
416         bcopy(cursor->data, ndata, elm->leaf.data_len);
417         hammer_modify_buffer_done(data_buffer);
418
419         hammer_blockmap_free(cursor->trans,
420                              elm->leaf.data_offset, elm->leaf.data_len);
421
422         hammer_modify_node(cursor->trans, cursor->node,
423                            &elm->leaf.data_offset, sizeof(hammer_off_t));
424         elm->leaf.data_offset = ndata_offset;
425         hammer_modify_node_done(cursor->node);
426
427 done:
428         if (data_buffer)
429                 hammer_rel_buffer(data_buffer, 0);
430         return (error);
431 }
432
433 /*
434  * Reblock a B-Tree leaf node.  The parent must be adjusted to point to
435  * the new copy of the leaf node.
436  *
437  * elm is a pointer to the parent element pointing at cursor.node.
438  */
439 static int
440 hammer_reblock_leaf_node(struct hammer_ioc_reblock *reblock,
441                          hammer_cursor_t cursor, hammer_btree_elm_t elm)
442 {
443         hammer_node_t onode;
444         hammer_node_t nnode;
445         int error;
446
447         /*
448          * Don't supply a hint when allocating the leaf.  Fills are done
449          * from the leaf upwards.
450          */
451         onode = cursor->node;
452         nnode = hammer_alloc_btree(cursor->trans, 0, &error);
453
454         if (nnode == NULL)
455                 return (error);
456
457         /*
458          * Move the node
459          */
460         hammer_lock_ex(&nnode->lock);
461         hammer_modify_node_noundo(cursor->trans, nnode);
462         bcopy(onode->ondisk, nnode->ondisk, sizeof(*nnode->ondisk));
463
464         if (elm) {
465                 /*
466                  * We are not the root of the B-Tree 
467                  */
468                 hammer_modify_node(cursor->trans, cursor->parent,
469                                    &elm->internal.subtree_offset,
470                                    sizeof(elm->internal.subtree_offset));
471                 elm->internal.subtree_offset = nnode->node_offset;
472                 hammer_modify_node_done(cursor->parent);
473         } else {
474                 /*
475                  * We are the root of the B-Tree
476                  */
477                 hammer_volume_t volume;
478                         
479                 volume = hammer_get_root_volume(cursor->trans->hmp, &error);
480                 KKASSERT(error == 0);
481
482                 hammer_modify_volume_field(cursor->trans, volume,
483                                            vol0_btree_root);
484                 volume->ondisk->vol0_btree_root = nnode->node_offset;
485                 hammer_modify_volume_done(volume);
486                 hammer_rel_volume(volume, 0);
487         }
488
489         hammer_cursor_replaced_node(onode, nnode);
490         hammer_delete_node(cursor->trans, onode);
491
492         if (hammer_debug_general & 0x4000) {
493                 kprintf("REBLOCK LNODE %016llx -> %016llx\n",
494                         (long long)onode->node_offset,
495                         (long long)nnode->node_offset);
496         }
497         hammer_modify_node_done(nnode);
498         cursor->node = nnode;
499
500         hammer_unlock(&onode->lock);
501         hammer_rel_node(onode);
502
503         return (error);
504 }
505
506 /*
507  * Reblock a B-Tree internal node.  The parent must be adjusted to point to
508  * the new copy of the internal node, and the node's children's parent
509  * pointers must also be adjusted to point to the new copy.
510  *
511  * elm is a pointer to the parent element pointing at cursor.node.
512  */
513 static int
514 hammer_reblock_int_node(struct hammer_ioc_reblock *reblock,
515                          hammer_cursor_t cursor, hammer_btree_elm_t elm)
516 {
517         struct hammer_node_lock lockroot;
518         hammer_node_t onode;
519         hammer_node_t nnode;
520         hammer_off_t hint;
521         int error;
522         int i;
523
524         hammer_node_lock_init(&lockroot, cursor->node);
525         error = hammer_btree_lock_children(cursor, 1, &lockroot, NULL);
526         if (error)
527                 goto done;
528
529         /*
530          * The internal node is visited after recursing through its
531          * first element.  Use the subtree offset allocated for that
532          * element as a hint for allocating the internal node.
533          */
534         onode = cursor->node;
535         if (onode->ondisk->count)
536                 hint = onode->ondisk->elms[0].internal.subtree_offset;
537         else
538                 hint = 0;
539         nnode = hammer_alloc_btree(cursor->trans, hint, &error);
540
541         if (nnode == NULL)
542                 goto done;
543
544         /*
545          * Move the node.  Adjust the parent's pointer to us first.
546          */
547         hammer_lock_ex(&nnode->lock);
548         hammer_modify_node_noundo(cursor->trans, nnode);
549         bcopy(onode->ondisk, nnode->ondisk, sizeof(*nnode->ondisk));
550
551         if (elm) {
552                 /*
553                  * We are not the root of the B-Tree 
554                  */
555                 hammer_modify_node(cursor->trans, cursor->parent,
556                                    &elm->internal.subtree_offset,
557                                    sizeof(elm->internal.subtree_offset));
558                 elm->internal.subtree_offset = nnode->node_offset;
559                 hammer_modify_node_done(cursor->parent);
560         } else {
561                 /*
562                  * We are the root of the B-Tree
563                  */
564                 hammer_volume_t volume;
565                         
566                 volume = hammer_get_root_volume(cursor->trans->hmp, &error);
567                 KKASSERT(error == 0);
568
569                 hammer_modify_volume_field(cursor->trans, volume,
570                                            vol0_btree_root);
571                 volume->ondisk->vol0_btree_root = nnode->node_offset;
572                 hammer_modify_volume_done(volume);
573                 hammer_rel_volume(volume, 0);
574         }
575
576         /*
577          * Now adjust our children's pointers to us.
578          */
579         for (i = 0; i < nnode->ondisk->count; ++i) {
580                 elm = &nnode->ondisk->elms[i];
581                 error = btree_set_parent(cursor->trans, nnode, elm);
582                 if (error)
583                         panic("reblock internal node: fixup problem");
584         }
585
586         /*
587          * Clean up.
588          *
589          * The new node replaces the current node in the cursor.  The cursor
590          * expects it to be locked so leave it locked.  Discard onode.
591          */
592         hammer_cursor_replaced_node(onode, nnode);
593         hammer_delete_node(cursor->trans, onode);
594
595         if (hammer_debug_general & 0x4000) {
596                 kprintf("REBLOCK INODE %016llx -> %016llx\n",
597                         (long long)onode->node_offset,
598                         (long long)nnode->node_offset);
599         }
600         hammer_modify_node_done(nnode);
601         cursor->node = nnode;
602
603         hammer_unlock(&onode->lock);
604         hammer_rel_node(onode);
605
606 done:
607         hammer_btree_unlock_children(cursor->trans->hmp, &lockroot, NULL);
608         return (error);
609 }
610