2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
34 * $DragonFly: src/sys/vfs/hammer/Attic/hammer_spike.c,v 1.6 2008/01/11 01:41:34 dillon Exp $
40 * Load spike info given a cursor. The cursor must point to the leaf node
41 * that needs to be spiked.
44 hammer_load_spike(hammer_cursor_t cursor
, struct hammer_cursor
**spikep
)
46 hammer_cursor_t spike
;
48 KKASSERT(cursor
->node
->ondisk
->type
== HAMMER_BTREE_TYPE_LEAF
);
49 KKASSERT(*spikep
== NULL
);
50 *spikep
= spike
= kmalloc(sizeof(*spike
), M_HAMMER
, M_WAITOK
|M_ZERO
);
51 ++hammer_count_spikes
;
53 spike
->parent
= cursor
->parent
;
54 spike
->parent_index
= cursor
->parent_index
;
55 spike
->node
= cursor
->node
;
56 spike
->index
= cursor
->index
;
57 spike
->left_bound
= cursor
->left_bound
;
58 spike
->right_bound
= cursor
->right_bound
;
61 hammer_ref_node(spike
->parent
);
62 hammer_lock_ex(&spike
->parent
->lock
);
64 hammer_ref_node(spike
->node
);
65 hammer_lock_ex(&spike
->node
->lock
);
66 kprintf("LOAD SPIKE %p\n", spike
);
70 * Spike code - make room in a cluster by spiking in a new cluster.
72 * The spike structure contains a locked and reference B-Tree leaf node.
73 * The spike at a minimum must replace the node with a cluster reference
74 * and then delete the contents of the node.
76 * Various optimizations are desireable, including merging the spike node
77 * with an adjacent node that has already been spiked, if its cluster is
78 * not full, or promoting the spike node to the parent cluster of the current
79 * cluster when it represents the right hand boundary leaf node in the
80 * cluster (to avoid append chains).
83 hammer_spike(struct hammer_cursor
**spikep
)
85 hammer_cursor_t spike
;
86 struct hammer_cursor ncursor
;
87 hammer_cluster_t ocluster
;
88 hammer_cluster_t ncluster
;
90 hammer_record_ondisk_t rec
;
93 kprintf("hammer_spike: ENOSPC in cluster, spiking\n");
94 /*Debugger("ENOSPC");*/
97 * Lock and flush the cluster XXX
100 KKASSERT(spike
!= NULL
);
101 KKASSERT(spike
->parent
&&
102 spike
->parent
->cluster
== spike
->node
->cluster
);
106 ocluster
= onode
->cluster
;
107 hammer_lock_ex(&ocluster
->io
.lock
);
112 * Allocate and lock a new cluster, initialize its bounds.
114 ncluster
= hammer_alloc_cluster(ocluster
->volume
->hmp
, ocluster
,
116 if (ncluster
== NULL
)
118 hammer_init_cluster(ncluster
, spike
->left_bound
, spike
->right_bound
);
121 * Get a cursor for the new cluster. Operations will be limited to
124 error
= hammer_init_cursor_cluster(&ncursor
, ncluster
);
129 * Copy the elements in the leaf node.
131 for (spike
->index
= 0; spike
->index
< onode
->ondisk
->count
;
133 error
= hammer_btree_extract(spike
, HAMMER_CURSOR_GET_RECORD
|
134 HAMMER_CURSOR_GET_DATA
);
137 kprintf("EXTRACT %04x %016llx %016llx\n",
138 spike
->record
->base
.base
.rec_type
,
139 spike
->record
->base
.base
.obj_id
,
140 spike
->record
->base
.base
.key
);
141 error
= hammer_write_record(&ncursor
, spike
->record
,
142 spike
->data
, spike
->flags
);
143 if (error
== ENOSPC
) {
144 kprintf("impossible ENOSPC error on spike\n");
152 * Success! Replace the parent reference to the leaf node with a
153 * parent reference to the new cluster and fixup the new cluster's
154 * parent reference. This completes the spike operation.
157 hammer_node_ondisk_t ondisk
;
158 hammer_btree_elm_t elm
;
160 hammer_modify_node(spike
->parent
);
161 ondisk
= spike
->parent
->ondisk
;
162 elm
= &ondisk
->elms
[spike
->parent_index
];
163 elm
->internal
.subtree_type
= HAMMER_BTREE_TYPE_CLUSTER
;
164 elm
->internal
.rec_offset
= -1; /* XXX */
165 elm
->internal
.subtree_clu_no
= ncluster
->clu_no
;
166 elm
->internal
.subtree_vol_no
= ncluster
->volume
->vol_no
;
167 elm
->internal
.subtree_count
= onode
->ondisk
->count
; /*XXX*/
168 onode
->flags
|= HAMMER_NODE_MODIFIED
;
169 hammer_flush_node(onode
);
172 hammer_cluster_ondisk_t ondisk
;
174 hammer_modify_cluster(ncluster
);
175 ondisk
= ncluster
->ondisk
;
176 ondisk
->clu_btree_parent_vol_no
= ocluster
->volume
->vol_no
;
177 ondisk
->clu_btree_parent_clu_no
= ocluster
->clu_no
;
178 ondisk
->clu_btree_parent_offset
= spike
->parent
->node_offset
;
179 ondisk
->clu_btree_parent_clu_gen
= ocluster
->ondisk
->clu_gen
;
183 * Delete the records and data associated with the old leaf node,
184 * then free the old leaf node (nothing references it any more).
186 for (spike
->index
= 0; spike
->index
< onode
->ondisk
->count
;
188 hammer_btree_elm_t elm
;
191 elm
= &onode
->ondisk
->elms
[spike
->index
];
192 KKASSERT(elm
->leaf
.rec_offset
> 0);
193 hammer_free_record(ocluster
, elm
->leaf
.rec_offset
);
194 if (elm
->leaf
.data_offset
) {
195 roff
= elm
->leaf
.data_offset
- elm
->leaf
.rec_offset
;
196 if (roff
< 0 || roff
>= HAMMER_RECORD_SIZE
) {
197 hammer_free_data(ocluster
,
198 elm
->leaf
.data_offset
,
203 onode
->flags
|= HAMMER_NODE_DELETED
;
206 * Add a record representing the spike using space freed up by the
209 rec
= hammer_alloc_record(ocluster
, &error
, &spike
->record_buffer
);
210 KKASSERT(error
== 0);
211 rec
->spike
.base
.base
.rec_type
= HAMMER_RECTYPE_CLUSTER
;
212 rec
->spike
.clu_no
= ncluster
->clu_no
;
213 rec
->spike
.vol_no
= ncluster
->volume
->vol_no
;
214 rec
->spike
.clu_id
= 0;
217 * XXX I/O dependancy - new cluster must be flushed before current
218 * cluster can be flushed.
220 /*Debugger("COPY COMPLETE");*/
221 hammer_done_cursor(&ncursor
);
228 hammer_done_cursor(&ncursor
);
230 hammer_free_cluster(ncluster
);
232 hammer_unlock(&ncluster
->io
.lock
);
233 hammer_rel_cluster(ncluster
, 0);
235 kprintf("UNLOAD SPIKE %p %d\n", spike
, error
);
236 hammer_unlock(&ocluster
->io
.lock
);
237 hammer_done_cursor(spike
);
238 --hammer_count_spikes
;
239 kfree(spike
, M_HAMMER
);