Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * Copyright 2010 Couchbase, Inc
4 : : *
5 : : * Licensed under the Apache License, Version 2.0 (the "License");
6 : : * you may not use this file except in compliance with the License.
7 : : * You may obtain a copy of the License at
8 : : *
9 : : * http://www.apache.org/licenses/LICENSE-2.0
10 : : *
11 : : * Unless required by applicable law or agreed to in writing, software
12 : : * distributed under the License is distributed on an "AS IS" BASIS,
13 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : : * See the License for the specific language governing permissions and
15 : : * limitations under the License.
16 : : */
17 : :
18 : : #include <stdio.h>
19 : : #include <stdlib.h>
20 : : #include <string.h>
21 : :
22 : : #include "common.h"
23 : : #include "btreeblock.h"
24 : :
25 : : #include "memleak.h"
26 : :
27 : : #ifdef __DEBUG
28 : : #ifndef __DEBUG_BTREEBLOCK
29 : : #undef DBG
30 : : #undef DBGCMD
31 : : #undef DBGSW
32 : : #define DBG(...)
33 : : #define DBGCMD(...)
34 : : #define DBGSW(n, ...)
35 : : #endif
36 : : #endif
37 : :
38 : : struct btreeblk_addr{
39 : : void *addr;
40 : : struct list_elem le;
41 : : };
42 : :
43 : : struct btreeblk_block {
44 : : bid_t bid;
45 : : int sb_no;
46 : : uint32_t pos;
47 : : uint8_t dirty;
48 : : uint8_t age;
49 : : void *addr;
50 : : struct list_elem le;
51 : : struct avl_node avl;
52 : : #ifdef __BTREEBLK_BLOCKPOOL
53 : : struct btreeblk_addr *addr_item;
54 : : #endif
55 : : };
56 : :
57 : : #ifdef __BTREEBLK_READ_TREE
58 : : static int _btreeblk_bid_cmp(struct avl_node *a, struct avl_node *b, void *aux)
59 : : {
60 : : bid_t aa_bid, bb_bid;
61 : : struct btreeblk_block *aa, *bb;
62 : : aa = _get_entry(a, struct btreeblk_block, avl);
63 : : bb = _get_entry(b, struct btreeblk_block, avl);
64 : : aa_bid = aa->bid;
65 : : bb_bid = bb->bid;
66 : :
67 : : #ifdef __BIT_CMP
68 : : return _CMP_U64(aa_bid, bb_bid);
69 : : #else
70 : : if (aa->bid < bb->bid) {
71 : : return -1;
72 : : } else if (aa->bid > bb->bid) {
73 : : return 1;
74 : : } else {
75 : : return 0;
76 : : }
77 : : #endif
78 : : }
79 : : #endif
80 : :
81 : 7803495 : INLINE void _btreeblk_get_aligned_block(struct btreeblk_handle *handle,
82 : : struct btreeblk_block *block)
83 : : {
84 : : #ifdef __BTREEBLK_BLOCKPOOL
85 : : struct list_elem *e;
86 : :
87 : 7803495 : e = list_pop_front(&handle->blockpool);
88 [ + + ]: 7803103 : if (e) {
89 : 7799875 : block->addr_item = _get_entry(e, struct btreeblk_addr, le);
90 : 7799875 : block->addr = block->addr_item->addr;
91 : 7803103 : return;
92 : : }
93 : : // no free addr .. create
94 : : block->addr_item = (struct btreeblk_addr *)
95 : 3228 : mempool_alloc(sizeof(struct btreeblk_addr));
96 : : #endif
97 : :
98 : 3228 : malloc_align(block->addr, FDB_SECTOR_SIZE, handle->file->blocksize);
99 : : }
100 : :
101 : 7801230 : INLINE void _btreeblk_free_aligned_block(struct btreeblk_handle *handle,
102 : : struct btreeblk_block *block)
103 : : {
104 : : #ifdef __BTREEBLK_BLOCKPOOL
105 [ - + ]: 7801230 : assert(block->addr_item);
106 : : // sync addr & insert into pool
107 : 7801230 : block->addr_item->addr = block->addr;
108 : 7801230 : list_push_front(&handle->blockpool, &block->addr_item->le);
109 : 7801169 : block->addr_item = NULL;
110 : 7801169 : return;
111 : :
112 : : #endif
113 : :
114 : : free_align(block->addr);
115 : : }
116 : :
117 : 0 : INLINE int is_subblock(bid_t subbid)
118 : : {
119 : : uint8_t flag;
120 : 0 : flag = (subbid >> (8 * (sizeof(bid_t)-2))) & 0x00ff;
121 : 0 : return flag;
122 : : }
123 : :
124 : 5753 : INLINE void bid2subbid(bid_t bid, size_t subblock_no, size_t idx, bid_t *subbid)
125 : : {
126 : : bid_t flag;
127 : : // to distinguish subblock_no==0 to non-subblock
128 : 5753 : subblock_no++;
129 : 5753 : flag = (subblock_no << 5) | idx;
130 : 5753 : *subbid = bid | (flag << (8 * (sizeof(bid_t)-2)));
131 : 5753 : }
132 : 133294526 : INLINE void subbid2bid(bid_t subbid, size_t *subblock_no, size_t *idx, bid_t *bid)
133 : : {
134 : : uint8_t flag;
135 : 133294526 : flag = (subbid >> (8 * (sizeof(bid_t)-2))) & 0x00ff;
136 : 133294526 : *subblock_no = flag >> 5;
137 : : // to distinguish subblock_no==0 to non-subblock
138 : 133294526 : *subblock_no -= 1;
139 : 133294526 : *idx = flag & (0x20 - 0x01);
140 : 133294526 : *bid = ((bid_t)(subbid << 16)) >> 16;
141 : 133294526 : }
142 : :
143 : 91810 : INLINE void * _btreeblk_alloc(void *voidhandle, bid_t *bid, int sb_no)
144 : : {
145 : 91810 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
146 : 91810 : struct list_elem *e = list_end(&handle->alc_list);
147 : : struct btreeblk_block *block;
148 : : uint32_t curpos;
149 : :
150 [ + + ]: 91810 : if (e) {
151 : 1844 : block = _get_entry(e, struct btreeblk_block, le);
152 [ + + ]: 1844 : if (block->pos <= (handle->file->blocksize) - (handle->nodesize)) {
153 [ + - ]: 27 : if (filemgr_is_writable(handle->file, block->bid)) {
154 : 27 : curpos = block->pos;
155 : 27 : block->pos += (handle->nodesize);
156 : : *bid = block->bid * handle->nnodeperblock + curpos /
157 : 27 : (handle->nodesize);
158 : 27 : return ((uint8_t *)block->addr + curpos);
159 : : }
160 : : }
161 : : }
162 : :
163 : : // allocate new block from file manager
164 : 91783 : block = (struct btreeblk_block *)mempool_alloc(sizeof(struct btreeblk_block));
165 : 91783 : _btreeblk_get_aligned_block(handle, block);
166 : 91783 : block->sb_no = sb_no;
167 : 91783 : block->pos = handle->nodesize;
168 : 91783 : block->bid = filemgr_alloc(handle->file, handle->log_callback);
169 : 91783 : block->dirty = 1;
170 : 91783 : block->age = 0;
171 : :
172 : : #ifdef __CRC32
173 : 91783 : memset((uint8_t *)block->addr + handle->nodesize - BLK_MARKER_SIZE,
174 : 183566 : BLK_MARKER_BNODE, BLK_MARKER_SIZE);
175 : : #endif
176 : :
177 : : // btree bid differs to filemgr bid
178 : 91783 : *bid = block->bid * handle->nnodeperblock;
179 : 91783 : list_push_back(&handle->alc_list, &block->le);
180 : :
181 : 91783 : handle->nlivenodes++;
182 : :
183 : 91810 : return block->addr;
184 : : }
185 : 89950 : void * btreeblk_alloc(void *voidhandle, bid_t *bid) {
186 : 89950 : return _btreeblk_alloc(voidhandle, bid, -1);
187 : : }
188 : :
189 : :
190 : : #ifdef __ENDIAN_SAFE
191 : 8688953 : INLINE void _btreeblk_encode(struct btreeblk_handle *handle,
192 : : struct btreeblk_block *block)
193 : : {
194 : : size_t i, j, n, nsb, sb_size, offset;
195 : : void *addr;
196 : : struct bnode *node;
197 : : struct bnode **node_arr;
198 : :
199 [ + + ]: 17377933 : for (offset=0; offset<handle->nnodeperblock; ++offset) {
200 [ + + ]: 8688966 : if (block->sb_no > -1) {
201 : 46477 : nsb = handle->sb[block->sb_no].nblocks;
202 : 46477 : sb_size = handle->sb[block->sb_no].sb_size;
203 : : } else {
204 : 8642489 : nsb = 1;
205 : 8642489 : sb_size = 0;
206 : : }
207 : :
208 [ + + ]: 17856253 : for (i=0;i<nsb;++i) {
209 : : addr = (uint8_t*)block->addr +
210 : : (handle->nodesize) * offset +
211 : 9167273 : sb_size * i;
212 : 9167273 : node_arr = btree_get_bnode_array(addr, &n);
213 [ + + ]: 18334575 : for (j=0;j<n;++j){
214 : 9167288 : node = node_arr[j];
215 : 9167288 : node->flag = _endian_encode(node->flag);
216 : 9167288 : node->level = _endian_encode(node->level);
217 : 9167288 : node->nentry = _endian_encode(node->nentry);
218 : : }
219 : 9167287 : free(node_arr);
220 : : }
221 : : }
222 : 8688967 : }
223 : 16400098 : INLINE void _btreeblk_decode(struct btreeblk_handle *handle,
224 : : struct btreeblk_block *block)
225 : : {
226 : : size_t i, j, n, nsb, sb_size, offset;
227 : : void *addr;
228 : : struct bnode *node;
229 : : struct bnode **node_arr;
230 : :
231 [ + + ]: 32801465 : for (offset=0; offset<handle->nnodeperblock; ++offset) {
232 [ + + ]: 16400088 : if (block->sb_no > -1) {
233 : 60081 : nsb = handle->sb[block->sb_no].nblocks;
234 : 60081 : sb_size = handle->sb[block->sb_no].sb_size;
235 : : } else {
236 : 16340007 : nsb = 1;
237 : 16340007 : sb_size = 0;
238 : : }
239 : :
240 [ + + ]: 33606382 : for (i=0;i<nsb;++i) {
241 : : addr = (uint8_t*)block->addr +
242 : : (handle->nodesize) * offset +
243 : 17205015 : sb_size * i;
244 : 17205015 : node_arr = btree_get_bnode_array(addr, &n);
245 [ + + ]: 34412487 : for (j=0;j<n;++j){
246 : 17206193 : node = node_arr[j];
247 : 17206193 : node->flag = _endian_decode(node->flag);
248 : 17206193 : node->level = _endian_decode(node->level);
249 : 17206193 : node->nentry = _endian_decode(node->nentry);
250 : : }
251 : 17206294 : free(node_arr);
252 : : }
253 : : }
254 : 16401377 : }
255 : : #else
256 : : #define _btreeblk_encode(a,b)
257 : : #define _btreeblk_decode(a,b)
258 : : #endif
259 : :
260 : : INLINE void _btreeblk_free_dirty_block(struct btreeblk_handle *handle,
261 : : struct btreeblk_block *block);
262 : :
263 : 116203564 : INLINE void * _btreeblk_read(void *voidhandle, bid_t bid, int sb_no)
264 : : {
265 : 116203564 : struct list_elem *elm = NULL;
266 : 116203564 : struct btreeblk_block *block = NULL;
267 : 116203564 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
268 : : bid_t _bid, filebid;
269 : : int subblock;
270 : : int offset;
271 : : size_t sb, idx;
272 : :
273 : 116203564 : sb = idx = 0;
274 : 116203564 : subbid2bid(bid, &sb, &idx, &_bid);
275 : 116172976 : subblock = is_subblock(bid);
276 : 116158125 : filebid = _bid / handle->nnodeperblock;
277 : 116158125 : offset = _bid % handle->nnodeperblock;
278 : :
279 : : // check whether the block is in current lists
280 : : // read list (clean or dirty)
281 : : #ifdef __BTREEBLK_READ_TREE
282 : : // AVL-tree
283 : : // check first 3 elements in the list first,
284 : : // and then retrieve AVL-tree
285 : : size_t count = 0;
286 : : for (elm = list_begin(&handle->read_list);
287 : : (elm && count < 3); elm = list_next(elm)) {
288 : : block = _get_entry(elm, struct btreeblk_block, le);
289 : : if (block->bid == filebid) {
290 : : block->age = 0;
291 : : // move the elements to the front
292 : : list_remove(&handle->read_list, &block->le);
293 : : list_push_front(&handle->read_list, &block->le);
294 : : if (subblock) {
295 : : return (uint8_t *)block->addr +
296 : : (handle->nodesize) * offset +
297 : : handle->sb[sb].sb_size * idx;
298 : : } else {
299 : : return (uint8_t *)block->addr +
300 : : (handle->nodesize) * offset;
301 : : }
302 : : }
303 : : count++;
304 : : }
305 : :
306 : : struct btreeblk_block query;
307 : : query.bid = filebid;
308 : : struct avl_node *a;
309 : : a = avl_search(&handle->read_tree, &query.avl, _btreeblk_bid_cmp);
310 : : if (a) { // cache hit
311 : : block = _get_entry(a, struct btreeblk_block, avl);
312 : : block->age = 0;
313 : : // move the elements to the front
314 : : list_remove(&handle->read_list, &block->le);
315 : : list_push_front(&handle->read_list, &block->le);
316 : : if (subblock) {
317 : : return (uint8_t *)block->addr +
318 : : (handle->nodesize) * offset +
319 : : handle->sb[sb].sb_size * idx;
320 : : } else {
321 : : return (uint8_t *)block->addr +
322 : : (handle->nodesize) * offset;
323 : : }
324 : : }
325 : : #else
326 : : // list
327 [ + + ]: 1159297980 : for (elm = list_begin(&handle->read_list); elm; elm = list_next(elm)) {
328 : 1151726710 : block = _get_entry(elm, struct btreeblk_block, le);
329 [ + + ]: 1151726710 : if (block->bid == filebid) {
330 : 108586855 : block->age = 0;
331 [ + + ]: 108586855 : if (subblock) {
332 : : return (uint8_t *)block->addr +
333 : : (handle->nodesize) * offset +
334 : 37034154 : handle->sb[sb].sb_size * idx;
335 : : } else {
336 : : return (uint8_t *)block->addr +
337 : 71552701 : (handle->nodesize) * offset;
338 : : }
339 : : }
340 : : }
341 : : #endif
342 : :
343 : : // allocation list (dirty)
344 [ + + ]: 7710944 : for (elm = list_begin(&handle->alc_list); elm; elm = list_next(elm)) {
345 : 1810 : block = _get_entry(elm, struct btreeblk_block, le);
346 [ + + ][ + - ]: 1810 : if (block->bid == filebid &&
347 : : block->pos >= (handle->nodesize) * offset) {
348 : 1382 : block->age = 0;
349 [ + + ]: 1382 : if (subblock) {
350 : : return (uint8_t *)block->addr +
351 : : (handle->nodesize) * offset +
352 : 541 : handle->sb[sb].sb_size * idx;
353 : : } else {
354 : : return (uint8_t *)block->addr +
355 : 841 : (handle->nodesize) * offset;
356 : : }
357 : : }
358 : : }
359 : :
360 : : // there is no block in lists
361 : : // if miss, read from file and add item into read list
362 : 7712128 : block = (struct btreeblk_block *)mempool_alloc(sizeof(struct btreeblk_block));
363 [ + + ]: 7712128 : block->sb_no = (subblock)?(sb):(sb_no);
364 : 7712128 : block->pos = (handle->file->blocksize);
365 : 7712128 : block->bid = filebid;
366 : 7712128 : block->dirty = 0;
367 : 7712128 : block->age = 0;
368 : :
369 : 7712128 : _btreeblk_get_aligned_block(handle, block);
370 [ - + ]: 7711684 : if (filemgr_read(handle->file, block->bid, block->addr,
371 : 7711366 : handle->log_callback) != FDB_RESULT_SUCCESS) {
372 : 0 : _btreeblk_free_aligned_block(handle, block);
373 : 0 : mempool_free(block);
374 : 0 : return NULL;
375 : : }
376 : 7711684 : _btreeblk_decode(handle, block);
377 : :
378 : 7712285 : list_push_front(&handle->read_list, &block->le);
379 : : #ifdef __BTREEBLK_READ_TREE
380 : : avl_insert(&handle->read_tree, &block->avl, _btreeblk_bid_cmp);
381 : : #endif
382 : :
383 [ + + ]: 7712187 : if (subblock) {
384 : : return (uint8_t *)block->addr +
385 : : (handle->nodesize) * offset +
386 : 12368 : handle->sb[sb].sb_size * idx;
387 : : } else {
388 : 116300424 : return (uint8_t *)block->addr + (handle->nodesize) * offset;
389 : : }
390 : : }
391 : :
392 : 116170374 : void * btreeblk_read(void *voidhandle, bid_t bid)
393 : : {
394 : 116170374 : return _btreeblk_read(voidhandle, bid, -1);
395 : : }
396 : :
397 : : void btreeblk_set_dirty(void *voidhandle, bid_t bid);
398 : 36215 : void * btreeblk_move(void *voidhandle, bid_t bid, bid_t *new_bid)
399 : : {
400 : 36215 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
401 : : void *old_addr, *new_addr;
402 : : bid_t _bid, _new_bid;
403 : : int i, subblock;
404 : : size_t sb, idx, new_idx;
405 : :
406 : 36215 : old_addr = new_addr = NULL;
407 : 36215 : sb = idx = 0;
408 : 36215 : subbid2bid(bid, &sb, &idx, &_bid);
409 : 36215 : subblock = is_subblock(bid);
410 : :
411 [ + + ]: 36215 : if (!subblock) {
412 : : // normal block
413 : 34565 : old_addr = btreeblk_read(voidhandle, bid);
414 : 34565 : new_addr = btreeblk_alloc(voidhandle, new_bid);
415 : 34565 : handle->nlivenodes--;
416 : :
417 : : // move
418 : 34565 : memcpy(new_addr, old_addr, (handle->nodesize));
419 : :
420 : 34565 : filemgr_invalidate_block(handle->file, bid);
421 : 34565 : return new_addr;
422 : : } else {
423 : : // subblock
424 [ + + ]: 1650 : if (handle->sb[sb].bid == _bid) {
425 : : //2 case 1
426 : : // current subblock set is not writable
427 : : // move all of them
428 : 836 : old_addr = _btreeblk_read(voidhandle, _bid, sb);
429 : 836 : new_addr = _btreeblk_alloc(voidhandle, &_new_bid, sb);
430 : 836 : handle->nlivenodes--;
431 : 836 : handle->sb[sb].bid = _new_bid;
432 : 836 : bid2subbid(_new_bid, sb, idx, new_bid);
433 : :
434 : : // move
435 : 836 : memcpy(new_addr, old_addr, (handle->nodesize));
436 : :
437 : 836 : filemgr_invalidate_block(handle->file, _bid);
438 : 836 : return (uint8_t*)new_addr + handle->sb[sb].sb_size * idx;
439 : : } else {
440 : : //2 case 2
441 : : // move only the target subblock
442 : : // into current subblock set (no allocation is required)
443 : 814 : old_addr = _btreeblk_read(voidhandle, _bid, sb);
444 : :
445 : 814 : new_idx = handle->sb[sb].nblocks;
446 [ + + ]: 4635 : for (i=0;i<handle->sb[sb].nblocks;++i){
447 [ + + ]: 4556 : if (handle->sb[sb].bitmap[i] == 0) {
448 : 735 : new_idx = i;
449 : 735 : break;
450 : : }
451 : : }
452 [ + + + + ]: 1549 : if (new_idx == handle->sb[sb].nblocks ||
[ + + ]
453 : 735 : !filemgr_is_writable(handle->file, handle->sb[sb].bid)) {
454 : : // case 2-1
455 : : // no free slot OR not writable
456 : : // allocate new block
457 : 216 : new_addr = _btreeblk_alloc(voidhandle, &_new_bid, sb);
458 : 216 : handle->nlivenodes--;
459 : 216 : handle->sb[sb].bid = _new_bid;
460 : 216 : memset(handle->sb[sb].bitmap, 0, handle->sb[sb].nblocks);
461 : 216 : new_idx = 0;
462 : : } else {
463 : : // case 2-2
464 : : // append to the current block
465 : 598 : new_addr = _btreeblk_read(voidhandle, handle->sb[sb].bid, sb);
466 : 598 : btreeblk_set_dirty(voidhandle, handle->sb[sb].bid);
467 : : }
468 : :
469 : 814 : handle->sb[sb].bitmap[new_idx] = 1;
470 : 814 : bid2subbid(handle->sb[sb].bid, sb, new_idx, new_bid);
471 : :
472 : : // move
473 : 1628 : memcpy((uint8_t*)new_addr + handle->sb[sb].sb_size * new_idx,
474 : 814 : (uint8_t*)old_addr + handle->sb[sb].sb_size * idx,
475 : 3256 : handle->sb[sb].sb_size);
476 : :
477 : 36215 : return (uint8_t*)new_addr + handle->sb[sb].sb_size * new_idx;
478 : : }
479 : : }
480 : : }
481 : :
482 : 0 : void btreeblk_remove(void *voidhandle, bid_t bid)
483 : : {
484 : 0 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
485 : : bid_t _bid;
486 : : int i, subblock, nitems;
487 : : size_t sb, idx;
488 : :
489 : 0 : sb = idx = 0;
490 : 0 : subbid2bid(bid, &sb, &idx, &_bid);
491 : 0 : subblock = is_subblock(bid);
492 : :
493 [ # # ]: 0 : if (subblock) {
494 : : // subblock
495 [ # # ]: 0 : if (handle->sb[sb].bid == _bid) {
496 : : // erase bitmap
497 : 0 : handle->sb[sb].bitmap[idx] = 0;
498 : : // if all slots are empty, invalidate the block
499 : 0 : nitems = 0;
500 [ # # ]: 0 : for (i=0;i<handle->sb[sb].nblocks;++i){
501 [ # # ]: 0 : if (handle->sb[sb].bitmap) {
502 : 0 : nitems++;
503 : : }
504 : : }
505 [ # # ]: 0 : if (nitems == 0) {
506 : 0 : handle->sb[sb].bid = BLK_NOT_FOUND;
507 : 0 : handle->nlivenodes--;
508 : 0 : filemgr_invalidate_block(handle->file, _bid);
509 : : }
510 : : }
511 : : } else {
512 : : // normal block
513 : 0 : handle->nlivenodes--;
514 : 0 : filemgr_invalidate_block(handle->file, bid);
515 : : }
516 : 0 : }
517 : :
518 : 8636704 : int btreeblk_is_writable(void *voidhandle, bid_t bid)
519 : : {
520 : 8636704 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
521 : : bid_t _bid;
522 : : bid_t filebid;
523 : : size_t sb, idx;
524 : :
525 : 8636704 : sb = idx = 0;
526 : 8636704 : subbid2bid(bid, &sb, &idx, &_bid);
527 : 8636703 : filebid = _bid / handle->nnodeperblock;
528 : :
529 : 8636703 : return filemgr_is_writable(handle->file, filebid);
530 : : }
531 : :
532 : 8603092 : void btreeblk_set_dirty(void *voidhandle, bid_t bid)
533 : : {
534 : 8603092 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
535 : : struct list_elem *e;
536 : : struct btreeblk_block *block;
537 : : bid_t _bid;
538 : : bid_t filebid;
539 : : size_t sb, idx;
540 : :
541 : 8603092 : sb = idx = 0;
542 : 8603092 : subbid2bid(bid, &sb, &idx, &_bid);
543 : 8603091 : filebid = _bid / handle->nnodeperblock;
544 : :
545 : : #ifdef __BTREEBLK_READ_TREE
546 : : // AVL-tree
547 : : struct btreeblk_block query;
548 : : query.bid = filebid;
549 : : struct avl_node *a;
550 : : a = avl_search(&handle->read_tree, &query.avl, _btreeblk_bid_cmp);
551 : : if (a) {
552 : : block = _get_entry(a, struct btreeblk_block, avl);
553 : : block->dirty = 1;
554 : : }
555 : : #else
556 : : // list
557 : 8603091 : e = list_begin(&handle->read_list);
558 [ + + ]: 32771639 : while(e){
559 : 32769985 : block = _get_entry(e, struct btreeblk_block, le);
560 [ + + ]: 32769985 : if (block->bid == filebid) {
561 : 8601447 : block->dirty = 1;
562 : 8601447 : break;
563 : : }
564 : 24168538 : e = list_next(e);
565 : : }
566 : : #endif
567 : 8603101 : }
568 : :
569 : 160 : void _btreeblk_set_sb_no(void *voidhandle, bid_t bid, int sb_no)
570 : : {
571 : 160 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
572 : : struct list_elem *e;
573 : : struct btreeblk_block *block;
574 : : bid_t _bid;
575 : : bid_t filebid;
576 : : size_t sb, idx;
577 : :
578 : 160 : sb = idx = 0;
579 : 160 : subbid2bid(bid, &sb, &idx, &_bid);
580 : 160 : filebid = _bid / handle->nnodeperblock;
581 : :
582 : 160 : e = list_begin(&handle->alc_list);
583 [ + + ]: 160 : while(e){
584 : 5 : block = _get_entry(e, struct btreeblk_block, le);
585 [ + - ]: 5 : if (block->bid == filebid) {
586 : 5 : block->sb_no = sb_no;
587 : 5 : return;
588 : : }
589 : 0 : e = list_next(e);
590 : : }
591 : :
592 : : #ifdef __BTREEBLK_READ_TREE
593 : : // AVL-tree
594 : : struct btreeblk_block query;
595 : : query.bid = filebid;
596 : : struct avl_node *a;
597 : : a = avl_search(&handle->read_tree, &query.avl, _btreeblk_bid_cmp);
598 : : if (a) {
599 : : block = _get_entry(a, struct btreeblk_block, avl);
600 : : block->sb_no = sb_no;
601 : : }
602 : : #else
603 : : // list
604 : 155 : e = list_begin(&handle->read_list);
605 [ + - ]: 461 : while(e){
606 : 301 : block = _get_entry(e, struct btreeblk_block, le);
607 [ + + ]: 301 : if (block->bid == filebid) {
608 : 155 : block->sb_no = sb_no;
609 : 155 : return;
610 : : }
611 : 146 : e = list_next(e);
612 : : }
613 : : #endif
614 : : }
615 : :
616 : 8689388 : size_t btreeblk_get_size(void *voidhandle, bid_t bid)
617 : : {
618 : : bid_t _bid;
619 : : size_t sb, idx;
620 : 8689388 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
621 : :
622 [ + + ][ + + ]: 8689388 : if (is_subblock(bid) && bid != BLK_NOT_FOUND) {
[ + + ]
623 : 68182 : subbid2bid(bid, &sb, &idx, &_bid);
624 : 68182 : return handle->sb[sb].sb_size;
625 : : } else {
626 : 8689395 : return handle->nodesize;
627 : : }
628 : : }
629 : :
630 : 1999 : void * btreeblk_alloc_sub(void *voidhandle, bid_t *bid)
631 : : {
632 : : int i;
633 : : void *addr;
634 : 1999 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
635 : :
636 [ + + ]: 1999 : if (handle->nsb == 0) {
637 : 4 : return btreeblk_alloc(voidhandle, bid);
638 : : }
639 : :
640 : : // check current block is available
641 [ + + ]: 1995 : if (handle->sb[0].bid != BLK_NOT_FOUND) {
642 [ + + ]: 1821 : if (filemgr_is_writable(handle->file, handle->sb[0].bid)) {
643 : : // check if there is an empty slot
644 [ + + ]: 6346 : for (i=0;i<handle->sb[0].nblocks;++i){
645 [ + + ]: 6336 : if (handle->sb[0].bitmap[i] == 0) {
646 : : // return subblock
647 : 1809 : handle->sb[0].bitmap[i] = 1;
648 : 1809 : bid2subbid(handle->sb[0].bid, 0, i, bid);
649 : 1809 : addr = _btreeblk_read(voidhandle, handle->sb[0].bid, 0);
650 : 1809 : btreeblk_set_dirty(voidhandle, handle->sb[0].bid);
651 : : return (void*)
652 : : ((uint8_t*)addr +
653 : 1809 : handle->sb[0].sb_size * i);
654 : : }
655 : : }
656 : : }
657 : : }
658 : :
659 : : // existing subblock cannot be used .. give it up & allocate new one
660 : 186 : addr = _btreeblk_alloc(voidhandle, &handle->sb[0].bid, 0);
661 : 186 : memset(handle->sb[0].bitmap, 0, handle->sb[0].nblocks);
662 : 186 : i = 0;
663 : 186 : handle->sb[0].bitmap[i] = 1;
664 : 186 : bid2subbid(handle->sb[0].bid, 0, i, bid);
665 : 1999 : return (void*)((uint8_t*)addr + handle->sb[0].sb_size * i);
666 : : }
667 : :
668 : 2576 : void * btreeblk_enlarge_node(void *voidhandle,
669 : : bid_t old_bid,
670 : : size_t req_size,
671 : : bid_t *new_bid)
672 : : {
673 : : int i;
674 : : bid_t bid;
675 : : size_t src_sb, src_idx, src_nitems;
676 : : size_t dst_sb, dst_idx, dst_nitems;
677 : : void *src_addr, *dst_addr;
678 : 2576 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
679 : :
680 [ - + ]: 2576 : if (!is_subblock(old_bid)) {
681 : 0 : return NULL;
682 : : }
683 : 2576 : src_addr = dst_addr = NULL;
684 : 2576 : subbid2bid(old_bid, &src_sb, &src_idx, &bid);
685 : :
686 : 2576 : dst_sb = 0;
687 : : // find sublock that can accommodate req_size
688 [ + + ]: 3786 : for (i=src_sb+1; i<handle->nsb; ++i){
689 [ + + ]: 3318 : if (handle->sb[i].sb_size > req_size) {
690 : 2108 : dst_sb = i;
691 : 2108 : break;
692 : : }
693 : : }
694 : :
695 : 2576 : src_nitems = 0;
696 [ + + ]: 61754 : for (i=0;i<handle->sb[src_sb].nblocks;++i){
697 [ + + ]: 59178 : if (handle->sb[src_sb].bitmap[i]) {
698 : 6993 : src_nitems++;
699 : : }
700 : : }
701 : :
702 : 2576 : dst_nitems = 0;
703 [ + + ]: 2576 : if (dst_sb > 0) {
704 : 2108 : dst_idx = handle->sb[dst_sb].nblocks;
705 [ + + ]: 26680 : for (i=0;i<handle->sb[dst_sb].nblocks;++i){
706 [ + + ]: 24572 : if (handle->sb[dst_sb].bitmap[i]) {
707 : 8133 : dst_nitems++;
708 [ + + ]: 16439 : } else if (dst_idx == handle->sb[dst_sb].nblocks) {
709 : 2037 : dst_idx = i;
710 : : }
711 : : }
712 : : }
713 : :
714 [ + + ]: 2576 : if (dst_nitems == 0) {
715 : : // destination block is empty
716 : 1080 : dst_idx = 0;
717 [ + + ]: 1080 : if (src_nitems == 1) {
718 : : //2 case 1
719 : : // if there's only one subblock in the source block,
720 : : // then switch source block to destination block
721 : 193 : src_addr = _btreeblk_read(voidhandle, bid, src_sb);
722 [ + + ][ + + ]: 193 : if (filemgr_is_writable(handle->file, bid) &&
[ + + ]
723 : 163 : bid == handle->sb[src_sb].bid) {
724 : : // case 1-1
725 : 160 : dst_addr = src_addr;
726 [ + + ]: 160 : if (dst_sb > 0) {
727 : 74 : handle->sb[dst_sb].bid = handle->sb[src_sb].bid;
728 : : } else {
729 : 86 : *new_bid = handle->sb[src_sb].bid;
730 : : }
731 : 160 : btreeblk_set_dirty(voidhandle, handle->sb[src_sb].bid);
732 : : // we MUST change block->sb_no value since subblock is switched.
733 : : // dst_sb == 0: regular block, otherwise: sub-block
734 : 160 : _btreeblk_set_sb_no(voidhandle, handle->sb[src_sb].bid,
735 [ + + ]: 160 : ((dst_sb)?(dst_sb):(-1)));
736 : : } else {
737 : : // case 1-2
738 : : // if the source block is not writable, allocate new one
739 [ + + ]: 33 : if (dst_sb > 0) {
740 : : dst_addr = _btreeblk_alloc(voidhandle,
741 : 23 : &handle->sb[dst_sb].bid, dst_sb);
742 : : } else {
743 : : // normal (whole) block
744 : 10 : dst_addr = btreeblk_alloc(voidhandle, new_bid);
745 : : }
746 : : }
747 : :
748 [ + + ][ + + ]: 193 : if (src_idx > 0 || dst_addr != src_addr) {
749 : : // move node to the beginning of the block
750 : : memmove(dst_addr,
751 : 94 : (uint8_t*)src_addr + handle->sb[src_sb].sb_size * src_idx,
752 : 94 : handle->sb[src_sb].sb_size);
753 : : }
754 [ + + ]: 193 : if (dst_sb > 0) {
755 : 97 : handle->sb[dst_sb].bitmap[dst_idx] = 1;
756 : : }
757 [ + + ]: 193 : if (bid == handle->sb[src_sb].bid) {
758 : : // remove existing source block info
759 : 186 : handle->sb[src_sb].bid = BLK_NOT_FOUND;
760 : 186 : memset(handle->sb[src_sb].bitmap, 0,
761 : 186 : handle->sb[src_sb].nblocks);
762 : : }
763 : :
764 : : } else {
765 : : //2 case 2
766 : : // if there are more than one slubblocks in the source block,
767 : : // then allocate destination block and move the target subblock
768 : 887 : src_addr = _btreeblk_read(voidhandle, bid, src_sb);
769 : :
770 [ + + ]: 887 : if (dst_sb > 0) {
771 : : // case 2-1
772 : 515 : dst_addr = _btreeblk_alloc(voidhandle, &handle->sb[dst_sb].bid, dst_sb);
773 : 1030 : memcpy((uint8_t*)dst_addr + handle->sb[dst_sb].sb_size * dst_idx,
774 : 515 : (uint8_t*)src_addr + handle->sb[src_sb].sb_size * src_idx,
775 : 2060 : handle->sb[src_sb].sb_size);
776 : 515 : handle->sb[dst_sb].bitmap[dst_idx] = 1;
777 : : } else {
778 : : // case 2-2: normal (whole) block
779 : 372 : dst_addr = btreeblk_alloc(voidhandle, new_bid);
780 : : memcpy((uint8_t*)dst_addr,
781 : 372 : (uint8_t*)src_addr + handle->sb[src_sb].sb_size * src_idx,
782 : 372 : handle->sb[src_sb].sb_size);
783 : : }
784 [ + + ]: 887 : if (bid == handle->sb[src_sb].bid) {
785 : 880 : handle->sb[src_sb].bitmap[src_idx] = 0;
786 : : }
787 : : }
788 : : } else {
789 : : //2 case 3
790 : : // destination block exists (always happens when subblock)
791 : 1496 : src_addr = _btreeblk_read(voidhandle, bid, src_sb);
792 [ + + ][ + + ]: 1496 : if (filemgr_is_writable(handle->file, handle->sb[dst_sb].bid) &&
[ + + ]
793 : 1482 : dst_idx != handle->sb[dst_sb].nblocks) {
794 : : // case 3-1
795 : 1412 : dst_addr = _btreeblk_read(voidhandle, handle->sb[dst_sb].bid, dst_sb);
796 : : } else {
797 : : // case 3-2: allocate new destination block
798 : 84 : dst_addr = _btreeblk_alloc(voidhandle, &handle->sb[dst_sb].bid, dst_sb);
799 : 84 : memset(handle->sb[dst_sb].bitmap, 0, handle->sb[dst_sb].nblocks);
800 : 84 : dst_idx = 0;
801 : : }
802 : :
803 : 2992 : memcpy((uint8_t*)dst_addr + handle->sb[dst_sb].sb_size * dst_idx,
804 : 1496 : (uint8_t*)src_addr + handle->sb[src_sb].sb_size * src_idx,
805 : 5984 : handle->sb[src_sb].sb_size);
806 : 1496 : handle->sb[dst_sb].bitmap[dst_idx] = 1;
807 [ + + ]: 1496 : if (bid == handle->sb[src_sb].bid) {
808 : 1470 : handle->sb[src_sb].bitmap[src_idx] = 0;
809 : : }
810 : : }
811 : :
812 [ + + ]: 2576 : if (dst_sb > 0) {
813 : : // sub block
814 : 2108 : bid2subbid(handle->sb[dst_sb].bid, dst_sb, dst_idx, new_bid);
815 : 2108 : return (uint8_t*)dst_addr + handle->sb[dst_sb].sb_size * dst_idx;
816 : : } else {
817 : : // whole block
818 : 2576 : return dst_addr;
819 : : }
820 : : }
821 : :
822 : 7801520 : INLINE void _btreeblk_free_dirty_block(struct btreeblk_handle *handle,
823 : : struct btreeblk_block *block)
824 : : {
825 : 7801520 : _btreeblk_free_aligned_block(handle, block);
826 : 7801003 : mempool_free(block);
827 : 7801003 : }
828 : :
829 : 8688950 : INLINE fdb_status _btreeblk_write_dirty_block(struct btreeblk_handle *handle,
830 : : struct btreeblk_block *block)
831 : : {
832 : : fdb_status status;
833 : : //2 MUST BE modified to support multiple nodes in a block
834 : :
835 : 8688950 : _btreeblk_encode(handle, block);
836 : : status = filemgr_write(handle->file, block->bid, block->addr,
837 : 8688967 : handle->log_callback);
838 : 8688964 : _btreeblk_decode(handle, block);
839 : 8688964 : return status;
840 : : }
841 : :
842 : 16491384 : fdb_status btreeblk_operation_end(void *voidhandle)
843 : : {
844 : : // flush and write all items in allocation list
845 : 16491384 : struct btreeblk_handle *handle = (struct btreeblk_handle *)voidhandle;
846 : : struct list_elem *e;
847 : : struct btreeblk_block *block;
848 : : int writable;
849 : 16491384 : fdb_status status = FDB_RESULT_SUCCESS;
850 : :
851 : : // write and free items in allocation list
852 : 16491384 : e = list_begin(&handle->alc_list);
853 [ + + ]: 16584058 : while(e){
854 : 91775 : block = _get_entry(e, struct btreeblk_block, le);
855 : 91775 : writable = filemgr_is_writable(handle->file, block->bid);
856 [ + - ]: 91775 : if (writable) {
857 : 91775 : status = _btreeblk_write_dirty_block(handle, block);
858 [ + + ]: 91775 : if (status != FDB_RESULT_SUCCESS) {
859 : 3 : return status;
860 : : }
861 : : }else{
862 : 0 : assert(0);
863 : : }
864 : :
865 [ + + ][ - + ]: 91772 : if (block->pos + (handle->nodesize) > (handle->file->blocksize) || !writable) {
866 : : // remove from alc_list and insert into read list
867 : 91770 : e = list_remove(&handle->alc_list, &block->le);
868 : 91770 : block->dirty = 0;
869 : 91770 : list_push_front(&handle->read_list, &block->le);
870 : : #ifdef __BTREEBLK_READ_TREE
871 : : avl_insert(&handle->read_tree, &block->avl, _btreeblk_bid_cmp);
872 : : #endif
873 : : }else {
874 : : // reserve the block when there is enough space and the block is writable
875 : 2 : e = list_next(e);
876 : : }
877 : : }
878 : :
879 : : // free items in read list
880 : : #ifdef __BTREEBLK_READ_TREE
881 : : // AVL-tree
882 : : struct avl_node *a;
883 : : a = avl_first(&handle->read_tree);
884 : : while (a) {
885 : : block = _get_entry(a, struct btreeblk_block, avl);
886 : : a = avl_next(a);
887 : :
888 : : if (block->dirty) {
889 : : // write back only when the block is modified
890 : : status = _btreeblk_write_dirty_block(handle, block);
891 : : if (status != FDB_RESULT_SUCCESS) {
892 : : return status;
893 : : }
894 : : block->dirty = 0;
895 : : }
896 : :
897 : : if (block->age >= BTREEBLK_AGE_LIMIT) {
898 : : list_remove(&handle->read_list, &block->le);
899 : : avl_remove(&handle->read_tree, &block->avl);
900 : : _btreeblk_free_dirty_block(handle, block);
901 : : } else {
902 : : block->age++;
903 : : }
904 : : }
905 : : #else
906 : : // list
907 : 16492283 : e = list_begin(&handle->read_list);
908 [ + + ]: 168587078 : while(e){
909 : 152095617 : block = _get_entry(e, struct btreeblk_block, le);
910 : :
911 [ + + ]: 152095617 : if (block->dirty) {
912 : : // write back only when the block is modified
913 : 8571738 : status = _btreeblk_write_dirty_block(handle, block);
914 [ - + ]: 8597187 : if (status != FDB_RESULT_SUCCESS) {
915 : 0 : return status;
916 : : }
917 : 8597187 : block->dirty = 0;
918 : : }
919 : :
920 [ + + ]: 152121066 : if (block->age >= BTREEBLK_AGE_LIMIT) {
921 : 7776530 : e = list_remove(&handle->read_list, &block->le);
922 : 7777616 : _btreeblk_free_dirty_block(handle, block);
923 : : } else {
924 : 144344536 : block->age++;
925 : 144344536 : e = list_next(e);
926 : : }
927 : : }
928 : : #endif
929 : 16491464 : return status;
930 : : }
931 : :
932 : 18073 : void btreeblk_discard_blocks(struct btreeblk_handle *handle)
933 : : {
934 : : // discard all writable blocks in the read list
935 : : struct list_elem *e;
936 : : struct btreeblk_block *block;
937 : :
938 : : // free items in read list
939 : : #ifdef __BTREEBLK_READ_TREE
940 : : // AVL-tree
941 : : struct avl_node *a;
942 : : a = avl_first(&handle->read_tree);
943 : : while (a) {
944 : : block = _get_entry(a, struct btreeblk_block, avl);
945 : : a = avl_next(a);
946 : :
947 : : list_remove(&handle->read_list, &block->le);
948 : : avl_remove(&handle->read_tree, &block->avl);
949 : : _btreeblk_free_dirty_block(handle, block);
950 : : }
951 : : #else
952 : : // list
953 : 18073 : e = list_begin(&handle->read_list);
954 [ + + ]: 40482 : while(e){
955 : 22409 : block = _get_entry(e, struct btreeblk_block, le);
956 : 22409 : e = list_next(&block->le);
957 : :
958 : 22409 : list_remove(&handle->read_list, &block->le);
959 : 22409 : _btreeblk_free_dirty_block(handle, block);
960 : : }
961 : : #endif
962 : 18073 : }
963 : :
964 : : #ifdef __BTREEBLK_SUBBLOCK
965 : : struct btree_blk_ops btreeblk_ops = {
966 : : btreeblk_alloc,
967 : : btreeblk_alloc_sub,
968 : : btreeblk_enlarge_node,
969 : : btreeblk_read,
970 : : btreeblk_move,
971 : : btreeblk_remove,
972 : : btreeblk_is_writable,
973 : : btreeblk_get_size,
974 : : btreeblk_set_dirty,
975 : : NULL
976 : : };
977 : : #else
978 : : struct btree_blk_ops btreeblk_ops = {
979 : : btreeblk_alloc,
980 : : NULL,
981 : : NULL,
982 : : btreeblk_read,
983 : : btreeblk_move,
984 : : btreeblk_remove,
985 : : btreeblk_is_writable,
986 : : btreeblk_get_size,
987 : : btreeblk_set_dirty,
988 : : NULL
989 : : };
990 : : #endif
991 : :
992 : 560 : struct btree_blk_ops *btreeblk_get_ops()
993 : : {
994 : 560 : return &btreeblk_ops;
995 : : }
996 : :
997 : 611 : void btreeblk_init(struct btreeblk_handle *handle, struct filemgr *file, int nodesize)
998 : : {
999 : : int i;
1000 : : uint32_t _nodesize;
1001 : :
1002 : 611 : handle->file = file;
1003 : 611 : handle->nodesize = nodesize;
1004 : 611 : handle->nnodeperblock = handle->file->blocksize / handle->nodesize;
1005 : 611 : handle->nlivenodes = 0;
1006 : :
1007 : 611 : list_init(&handle->alc_list);
1008 : 611 : list_init(&handle->read_list);
1009 : : #ifdef __BTREEBLK_READ_TREE
1010 : : avl_init(&handle->read_tree, NULL);
1011 : : #endif
1012 : :
1013 : : #ifdef __BTREEBLK_BLOCKPOOL
1014 : 611 : list_init(&handle->blockpool);
1015 : : #endif
1016 : :
1017 : : #ifdef __BTREEBLK_SUBBLOCK
1018 : : // compute # subblock sets
1019 : 611 : _nodesize = BTREEBLK_MIN_SUBBLOCK;
1020 [ + + ][ + - ]: 3628 : for (i=0; (_nodesize < nodesize && i<5); ++i){
[ + + ]
1021 : 3017 : _nodesize = _nodesize << 1;
1022 : : }
1023 : 611 : handle->nsb = i;
1024 [ + + ]: 611 : if (i) {
1025 : : handle->sb = (struct btreeblk_subblocks*)
1026 : 608 : malloc(sizeof(struct btreeblk_subblocks) * handle->nsb);
1027 : : // initialize each subblock set
1028 : 608 : _nodesize = BTREEBLK_MIN_SUBBLOCK;
1029 [ + + ]: 3625 : for (i=0;i<handle->nsb;++i){
1030 : 3017 : handle->sb[i].bid = BLK_NOT_FOUND;
1031 : 3017 : handle->sb[i].sb_size = _nodesize;
1032 : 3017 : handle->sb[i].nblocks = nodesize / _nodesize;
1033 : 3017 : handle->sb[i].bitmap = (uint8_t*)malloc(handle->sb[i].nblocks);
1034 : 3017 : memset(handle->sb[i].bitmap, 0, handle->sb[i].nblocks);
1035 : 3017 : _nodesize = _nodesize << 1;
1036 : : }
1037 : : } else {
1038 : 3 : handle->sb = NULL;
1039 : : }
1040 : : #endif
1041 : 611 : }
1042 : :
1043 : : // shutdown
1044 : 607 : void btreeblk_free(struct btreeblk_handle *handle)
1045 : : {
1046 : : struct list_elem *e;
1047 : : struct btreeblk_block *block;
1048 : :
1049 : : // free all blocks in alc list
1050 : 607 : e = list_begin(&handle->alc_list);
1051 [ + + ]: 613 : while(e) {
1052 : 6 : block = _get_entry(e, struct btreeblk_block, le);
1053 : 6 : e = list_remove(&handle->alc_list, &block->le);
1054 : 6 : _btreeblk_free_dirty_block(handle, block);
1055 : : }
1056 : :
1057 : : // free all blocks in read list
1058 : : #ifdef __BTREEBLK_READ_TREE
1059 : : // AVL tree
1060 : : struct avl_node *a;
1061 : : a = avl_first(&handle->read_tree);
1062 : : while (a) {
1063 : : block = _get_entry(a, struct btreeblk_block, avl);
1064 : : a = avl_next(a);
1065 : : avl_remove(&handle->read_tree, &block->avl);
1066 : : _btreeblk_free_dirty_block(handle, block);
1067 : : }
1068 : : #else
1069 : : // linked list
1070 : 607 : e = list_begin(&handle->read_list);
1071 [ + + ]: 2165 : while(e) {
1072 : 1558 : block = _get_entry(e, struct btreeblk_block, le);
1073 : 1558 : e = list_remove(&handle->read_list, &block->le);
1074 : 1558 : _btreeblk_free_dirty_block(handle, block);
1075 : : }
1076 : : #endif
1077 : :
1078 : : #ifdef __BTREEBLK_BLOCKPOOL
1079 : : // free all blocks in the block pool
1080 : : struct btreeblk_addr *item;
1081 : :
1082 : 607 : e = list_begin(&handle->blockpool);
1083 [ + + ]: 3817 : while(e){
1084 : 3210 : item = _get_entry(e, struct btreeblk_addr, le);
1085 : 3210 : e = list_next(e);
1086 : :
1087 : 3210 : free_align(item->addr);
1088 : 3210 : mempool_free(item);
1089 : : }
1090 : : #endif
1091 : :
1092 : : #ifdef __BTREEBLK_SUBBLOCK
1093 : : int i;
1094 [ + + ]: 3618 : for (i=0;i<handle->nsb;++i){
1095 : 3011 : free(handle->sb[i].bitmap);
1096 : : }
1097 : 607 : free(handle->sb);
1098 : : #endif
1099 : 607 : }
1100 : :
1101 : 16492133 : fdb_status btreeblk_end(struct btreeblk_handle *handle)
1102 : : {
1103 : : struct list_elem *e;
1104 : : struct btreeblk_block *block;
1105 : 16492133 : fdb_status status = FDB_RESULT_SUCCESS;
1106 : :
1107 : : // flush all dirty items
1108 : 16492133 : status = btreeblk_operation_end((void *)handle);
1109 [ + + ]: 16491362 : if (status != FDB_RESULT_SUCCESS) {
1110 : 3 : return status;
1111 : : }
1112 : :
1113 : : // remove all items in lists
1114 : 16491359 : e = list_begin(&handle->alc_list);
1115 [ + + ]: 16490882 : while(e) {
1116 : 2 : block = _get_entry(e, struct btreeblk_block, le);
1117 : 2 : e = list_remove(&handle->alc_list, &block->le);
1118 : :
1119 : 2 : block->dirty = 0;
1120 : 2 : list_push_front(&handle->read_list, &block->le);
1121 : : #ifdef __BTREEBLK_READ_TREE
1122 : : avl_insert(&handle->read_tree, &block->avl, _btreeblk_bid_cmp);
1123 : : #endif
1124 : : }
1125 : 16490883 : return status;
1126 : : }
|
