1 | /* onode_index.c
2 | -------------
3 | A casually demented B+Tree designed to stay balanced
4 | and be optimized for access from disk (and in-core cache)
5 |
6 | $Id: onode_index.c,v 1.15 2003/10/20 07:18:11 stewart Exp $
7 |
8 | (C)2003 Stewart Smith
9 | Distributed under the GNU Public License
10 | */
11 | #include <stdio.h>
12 | #include <stdlib.h>
13 | #include <string.h>
14 | #include "testkit/types.h"
15 |
16 | #include "disk.h"
17 | #include "super_block.h"
18 | #include "space_bitmap.h"
19 | #include "onode_index.h"
20 |
21 | extern u64 next_free;
22 |
23 | u64 onode_index_new_id(struct fcfs_onode_index *index)
24 | {
25 |
26 | }
27 |
28 | struct fcfs_onode_index* onode_index_read(struct fcfs_disk *disk)
29 | {
30 | struct fcfs_onode_index *index;
31 | struct fcfs_disk_block *block;
32 |
33 | index = (struct fcfs_onode_index*)malloc(sizeof(struct fcfs_onode_index));
34 | if(index==NULL)
35 | {fprintf(stderr,"Cannot allocate onode index structure to read into\n");
36 | abort();}
37 | block = disk_getblock(disk,disk->sb->onode_index_blocknr);
38 | index->root_block = block;
39 | index->root = (struct fcfs_onode_index_node*)block->data;
40 |
41 | index->disk = disk;
42 |
43 | return index;
44 | }
45 |
46 | struct fcfs_onode_index* onode_index_new(struct fcfs_disk *disk)
47 | {
48 | struct fcfs_onode_index *index;
49 |
50 | index = (struct fcfs_onode_index*)malloc(sizeof(struct fcfs_onode_index));
51 | if(index==NULL)
52 | {fprintf(stderr,"Cannot allocate onode index structure\n"); abort();}
53 |
54 | index->root = NULL;
55 | index->disk = disk;
56 |
57 | return index;
58 | }
59 |
60 | int onode_index_write_leaf(struct fcfs_onode_index *index, struct fcfs_onode_index_leaf *leaf)
61 | {
62 | struct fcfs_disk_block *block;
63 |
64 | block = disk_getblock(index->disk,leaf->block);
65 | #ifdef DEBUG_ONODE_INDEX
66 | fprintf(stderr,"--WRITE LEAF--\n");
67 | #endif
68 | disk_writeblock(block);
69 | disk_freeblock(block);
70 |
71 | return 1;
72 | }
73 |
74 | struct fcfs_onode_index_leaf *onode_index_leaf_new(struct fcfs_onode_index *index, struct fcfs_onode_index_node *parent, int position)
75 | {
76 | int i;
77 | struct fcfs_block_run *br;
78 | struct fcfs_onode_index_leaf *leaf;
79 | struct fcfs_disk_block *block;
80 |
81 | // printf("onode_index_leaf_new\n");
82 | br = ag_allocate_block(index->disk,
83 | BLOCK_AG(index->disk,parent->block),
84 | parent->block%index->disk->sb->ag_blocksnr,
85 | 1);
86 | block = disk_newblock(index->disk,BR_SECTOR_T(index->disk,br));
87 | leaf = (struct fcfs_onode_index_leaf*)block->data;
88 |
89 | #ifdef DEBUG_ONODE_INDEX
90 | fprintf(stderr,"LEAF: AG: %d, Start: %d, Len: %d\n",br->allocation_group,br->start,br->len);
91 | #endif
92 |
93 | leaf->magic1 = FCFS_ONODE_INDEX_LEAF_MAGIC1;
94 | leaf->id = index->disk->sb->onindex_next_id++;
95 | leaf->block = BR_SECTOR_T(index->disk,br);
96 | leaf->used = 0ULL;
97 |
98 | for(i=0;i<index->disk->sb->onindex_node_size;i++)
99 | { leaf->items[i].key = 0; leaf->items[i].onode_blocknr = 0; }
100 |
101 | onode_index_write_leaf(index,leaf);
102 |
103 | parent->items[position].node_blocknr = BR_SECTOR_T(index->disk,br);
104 | if(parent->used < position)
105 | parent->used = position;
106 |
107 | onode_index_write_node(index,parent);
108 |
109 | free(br);
110 | return leaf;
111 | }
112 |
113 | struct fcfs_onode_index_node* onode_index_read_node(struct fcfs_onode_index *index, u64 blocknr)
114 | {
115 | struct fcfs_onode_index_node* node;
116 | struct fcfs_disk_block *block;
117 |
118 | block = disk_getblock(index->disk, blocknr);
119 |
120 | node = (struct fcfs_onode_index_node*) block->data;
121 |
122 | return node;
123 | }
124 |
125 | int onode_index_free_node(struct fcfs_onode_index *index, struct fcfs_onode_index_node* node)
126 | {
127 | struct fcfs_disk_block *block;
128 | block = disk_getblock(index->disk,node->block);
129 | disk_freeblock(block);
130 | free(node);
131 | return 1;
132 | }
133 |
134 | int onode_index_write_node(struct fcfs_onode_index *index, struct fcfs_onode_index_node* node)
135 | {
136 | struct fcfs_disk_block *block;
137 |
138 | /* Write root to disk */
139 | block = disk_getblock(index->disk,node->block);
140 | disk_writeblock(block);
141 | #ifdef DEBUG_ONODE_INDEX
142 | fprintf(stderr,"--WRITE NODE--\n");
143 | #endif
144 | disk_freeblock(block);
145 |
146 | return 1;
147 | }
148 |
149 | /* Writes root back to disk */
150 | static inline int onode_index_write_root(struct fcfs_onode_index *index)
151 | {
152 | return onode_index_write_node(index,index->root);
153 | }
154 |
155 | /* The ever belated onode_index_new_node */
156 | struct fcfs_disk_block *onode_index_new_node(struct fcfs_onode_index *index)
157 | {
158 | struct fcfs_block_run *br;
159 | struct fcfs_disk_block *block;
160 | struct fcfs_onode_index_node *node;
161 | int i;
162 |
163 | br = ag_allocate_block(index->disk,0,1,1);
164 | if((br->len) < 1)
165 | {
166 | fprintf(stderr,"Unable to allocate Onode Index Node\n");
167 | fprintf(stderr,"\tAG: %d, Start: %d, Len: %d\n",br->allocation_group,br->start,br->len);
168 | abort();
169 | }
170 |
171 | fprintf(stderr,"Onode Index node created at: AG: %d, Start: %d, Len: %d\n",br->allocation_group,br->start,br->len);
172 |
173 | block = disk_newblock(index->disk,BR_SECTOR_T(index->disk,br));
174 | node = (struct fcfs_onode_index_node*)block->data;
175 |
176 | node->magic1 = FCFS_ONODE_INDEX_NODE_MAGIC1;
177 | node->id = index->disk->sb->onindex_next_id++;
178 | node->used = 0ULL;
179 | node->block = br->start;
180 |
181 | for(i=0;i<index->disk->sb->onindex_node_size;i++)
182 | { node->items[i].key = 0; node->items[i].node_blocknr = 0;}
183 |
184 | return block;
185 | }
186 |
187 | /* Creates a new root node for an onode_index */
188 | int onode_index_new_root(struct fcfs_onode_index *index)
189 | {
190 | struct fcfs_onode_index_node *node;
191 | struct fcfs_disk_block *block;
192 |
193 | block = onode_index_new_node(index);
194 | index->root = (struct fcfs_onode_index_node*)block->data;
195 | index->root_block = block;
196 |
197 | fprintf(stderr,"****ONODE INDEX**** %llu\n",block->blocknr);
198 |
199 | /* Move br to index structure */
200 | /* Also copy into super block, and write to disk */
201 | /* update the SB records */
202 | index->disk->sb->onode_index_blocknr = block->blocknr;
203 | index->disk->sb->onindex_free = index->disk->sb->onindex_node_size;
204 | fcfs_write_sb(index->disk);
205 | onode_index_write_root(index);
206 |
207 | return 1;
208 | }
209 |
210 | int onode_index_leaf_insert(struct fcfs_disk *disk,struct fcfs_onode_index_leaf *leaf, u64 key, u64 value)
211 | {
212 | int pos;
213 | int i;
214 |
215 | if(leaf->used==disk->sb->onindex_node_size)
216 | { /* Need to split leaf */
217 | fprintf(stderr,"onode_index_leaf_insert: full onode_index_leaf. Growing of leaves not yet implemented\n");
218 | abort();
219 | }
220 |
221 | if(key > leaf->items[leaf->used-1].key)
222 | { /* Append to end of leaf */
223 | leaf->used++; /* FIXME: should be atomic */
224 | leaf->items[leaf->used-1].key = key;
225 | leaf->items[leaf->used-1].onode_blocknr = value;
226 | return 1;
227 | }
228 | else
229 | {
230 | for(i=0;i<leaf->used && leaf->items[i].key < key;i++)
231 | ; /* FIXME: Make binary search */
232 | pos = i;
233 | leaf->used++;
234 | for(i=leaf->used;i>pos;i--) /* Shuffle everything down */
235 | {
236 | leaf->items[i].key = leaf->items[i-1].key;
237 | leaf->items[i].onode_blocknr = leaf->items[i-1].onode_blocknr;
238 | }
239 | leaf->items[pos].key = key; /* Add our key */
240 | leaf->items[pos].onode_blocknr = value; /* Add our value */
241 | return 1; /* Success! */
242 | }
243 |
244 | return 1;
245 | }
246 |
247 | /* Insert an onode into an index */
248 | struct fcfs_block_run* onode_index_insert(struct fcfs_onode_index *index, struct fcfs_onode1 *onode)
249 | {
250 | struct fcfs_block_run *onode_br;
251 | struct fcfs_disk_block *block;
252 | struct fcfs_onode_index_node *node;
253 | struct fcfs_onode_index_node *parent;
254 | struct fcfs_onode_index_leaf *leaf;
255 | int i,node_pos;
256 |
257 | if(index->root==NULL)
258 | onode_index_new_root(index);
259 |
260 | /* Determine ID for onode */
261 | // onode->onode_num = ((~0ULL)/index->disk->sb->onindex_node_size) * (i+1);
262 | onode->onode_num = random();
263 | //index->disk->sb->onindex_next_id++;
264 | fcfs_write_sb(index->disk);
265 |
266 | #ifdef DEBUG_ONODE_INDEX
267 | fprintf(stderr,"STORE ONODE ID: %llu\n",onode->onode_num);
268 | #endif
269 |
270 | /* Revision 1 now that we're going onto disk */
271 | onode->onode_revision = 1;
272 |
273 | /* Use count = 1, in onode_index */
274 | onode->use_count = 1;
275 |
276 | /* Allocate room for onode */
277 | // printf("onode_index_insert\n");
278 | onode_br = ag_allocate_block(index->disk,0,10,1);
279 |
280 | #ifdef DEBUG_ONODE_INDEX
281 | fprintf(stderr,"ONODE created at: AG: %d, Start: %d, Len: %d\n",onode_br->allocation_group,onode_br->start,onode_br->len);
282 | #endif
283 |
284 | /* Write onode to disk */
285 | block = disk_newblock(index->disk,BR_SECTOR_T(index->disk,onode_br));
286 | // memset(block->data,0,index->disk->bsize);
287 | memcpy(block->data,onode,sizeof(struct fcfs_onode1));
288 | disk_writeblock(block);
289 | #ifdef DEBUG_ONODE_INDEX
290 | fprintf(stderr,"ONODE Written\n");
291 | #endif
292 | disk_freeblock(block);
293 |
294 | /* Put it in the index properly */
295 | node = index->root;
296 | parent = NULL;
297 |
298 | /* Check current node for free space/location */
299 | for(i=0;i<node->used && node->items[i].key < onode->onode_num;i++)
300 | ; /* FIXME: This should be a binary search */
301 |
302 | if(i==index->disk->sb->onindex_node_size)
303 | i = 0;
304 |
305 | node_pos = i; /* position in the node */
306 |
307 | #ifdef DEBUG_ONODE_INDEX
308 | fprintf(stderr,"\n\n\ti = %d\n\n",i);
309 | #endif
310 |
311 | if(node->items[i].node_blocknr!=0)
312 | {
313 | /* Lookup subtree, see if node or leaf */
314 | parent = node;
315 | // node = ;
316 | block = disk_getblock(index->disk,node->items[i].node_blocknr);
317 | if(*((u64*)block->data)== FCFS_ONODE_INDEX_LEAF_MAGIC1)
318 | { /* is a leaf */
319 | #ifdef DEBUG_ONODE_INDEX
320 | fprintf(stderr,"FOUND A LEAF!\n\n");
321 | #endif
322 | leaf = (struct fcfs_onode_index_leaf *)block->data;
323 | #ifdef DEBUG_ONODE_INDEX
324 | fprintf(stderr,"GOING TO ADD TO LEAF 0x%llu\n",leaf->id);
325 | fprintf(stderr,"\tblock %llu\n",leaf->block);
326 | fprintf(stderr,"\tused %llu\n",leaf->used);
327 | #endif
328 |
329 | onode_index_leaf_insert(index->disk,leaf,
330 | onode->onode_num,
331 | BR_SECTOR_T(index->disk,
332 | onode_br));
333 |
334 | disk_writeblock(block);
335 | parent->items[node_pos].key = onode->onode_num;
336 | onode_index_write_node(index,parent);
337 | index->disk->sb->onindex_used++;
338 | index->disk->sb->onindex_free--;
339 | fcfs_write_sb(index->disk);
340 | }
341 | else if(*((u64*)block->data)== FCFS_ONODE_INDEX_NODE_MAGIC1)
342 | {
343 | fprintf(stderr,"FOUND A NODE!\n\n");
344 | fprintf(stderr,"**FIXME** We don't handle nodes yet\n");
345 | }
346 | else
347 | {
348 | fprintf(stderr,"WARNING-CORRUPT: node pointer points to corrupt node or leaf!\n");
349 | fprintf(stderr,"\tCORRUPT node->items[%d].node_blocknr = %llu\n",i,node->items[i].node_blocknr);
350 | fprintf(stderr,"\tMAGIC is %llx\n",*((u64*)block->data));
351 | abort();
352 | }
353 | disk_freeblock(block);
354 | }
355 | else
356 | {
357 | /* Create leaf */
358 | leaf = onode_index_leaf_new(index, node,i);
359 | leaf->items[0].key = onode->onode_num;
360 | leaf->items[0].onode_blocknr = BR_SECTOR_T(index->disk,onode_br);
361 | leaf->used = 1;
362 |
363 | #ifdef DEBUG_ONODE_INDEX
364 | fprintf(stderr,"LEAF: Should be writing with key=%lld, block=%lld\n",leaf->items[0].key,leaf->items[0].onode_blocknr);
365 | #endif
366 |
367 | node->items[i].node_blocknr = leaf->block;
368 | node->items[i].key = onode->onode_num;
369 | node->used = i+1;
370 |
371 | onode_index_write_root(index);
372 | onode_index_write_leaf(index,leaf);
373 | }
374 |
375 | return onode_br;
376 | }
377 |
378 | struct fcfs_disk_block *onode_index_lookup(struct fcfs_onode_index *index,struct fcfs_block_run *onode_br, u64 id)
379 | {
380 | struct fcfs_disk_block *block;
381 | struct fcfs_disk_block *onode_block;
382 | struct fcfs_onode_index_node *node;
383 | struct fcfs_onode_index_node *parent;
384 | struct fcfs_onode_index_leaf *leaf;
385 |
386 | int i;
387 |
388 | node = index->root;
389 |
390 | for(i=0;i<node->used && node->items[i].key < id ;i++)
391 | ;
392 |
393 | /* Lookup subtree, see if node or leaf */
394 | parent = node;
395 | // node = ;
396 | block = disk_getblock(index->disk,node->items[i].node_blocknr);
397 | if(*((u64*)block->data)== FCFS_ONODE_INDEX_LEAF_MAGIC1)
398 | { /* is a leaf */
399 | fprintf(stderr,"FOUND A LEAF!\n\n");
400 | leaf = (struct fcfs_onode_index_leaf *)block->data;
401 | fprintf(stderr,"READ LEAF 0x%llu\n",leaf->id);
402 | fprintf(stderr,"\tblock %llu\n",leaf->block);
403 | fprintf(stderr,"\tused %llu\n",leaf->used);
404 | for(i=0;i<leaf->used && leaf->items[i].key < id;i++)
405 | ;
406 | fprintf(stderr,"leaf i = %d, %llu %llu\n",i,leaf->items[i].key,leaf->items[i].onode_blocknr);
407 | onode_block = disk_getblock(index->disk,leaf->items[i].onode_blocknr);
408 | onode_br->allocation_group = BLOCK_AG(index->disk,leaf->items[i].onode_blocknr);
409 | onode_br->start = leaf->items[i].onode_blocknr%index->disk->sb->ag_blocksnr;
410 | onode_br->len = 1;
411 | disk_freeblock(block);
412 | }
413 | else
414 | abort();
415 |
416 | return onode_block;
417 | }
418 |
419 | struct fcfs_onode_index* onode_index_delete(struct fcfs_onode_index* index)
420 | {
421 | if(index->root)
422 | disk_freeblock(index->root_block);
423 | free(index);
424 | index = NULL;
425 | return index;
426 | }