Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2016, Citrix Systems, Inc.
3 : : *
4 : : * All rights reserved.
5 : : *
6 : : * Redistribution and use in source and binary forms, with or without
7 : : * modification, are permitted provided that the following conditions are met:
8 : : *
9 : : * 1. Redistributions of source code must retain the above copyright
10 : : * notice, this list of conditions and the following disclaimer.
11 : : * 2. Redistributions in binary form must reproduce the above copyright
12 : : * notice, this list of conditions and the following disclaimer in the
13 : : * documentation and/or other materials provided with the distribution.
14 : : * 3. Neither the name of the copyright holder nor the names of its
15 : : * contributors may be used to endorse or promote products derived from
16 : : * this software without specific prior written permission.
17 : : *
18 : : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 : : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 : : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 : : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
22 : : * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 : : * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 : : * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 : : * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26 : : * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27 : : * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 : : * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 : : */
30 : :
31 : : #ifdef HAVE_CONFIG_H
32 : : #include "config.h"
33 : : #endif
34 : :
35 : : #include <errno.h>
36 : : #include <fcntl.h>
37 : : #include <unistd.h>
38 : : #include <stdlib.h>
39 : : #include <sys/mman.h>
40 : :
41 : : #include "tapdisk.h"
42 : : #include "tapdisk-utils.h"
43 : : #include "tapdisk-driver.h"
44 : : #include "tapdisk-server.h"
45 : : #include "tapdisk-interface.h"
46 : : #include "timeout-math.h"
47 : :
48 : : #ifdef DEBUG
49 : : #define DBG(_f, _a...) tlog_write(TLOG_DBG, _f, ##_a)
50 : : #else
51 : : #define DBG(_f, _a...) ((void)0)
52 : : #endif
53 : :
54 : : #define WARN(_f, _a...) tlog_write(TLOG_WARN, _f, ##_a)
55 : :
56 : : #define RADIX_TREE_PAGE_SHIFT 12 /* 4K pages */
57 : : #define RADIX_TREE_PAGE_SIZE (1 << RADIX_TREE_PAGE_SHIFT)
58 : :
59 : : #define RADIX_TREE_NODE_SHIFT 9 /* 512B nodes */
60 : : #define RADIX_TREE_NODE_SIZE (1 << RADIX_TREE_NODE_SHIFT)
61 : : #define RADIX_TREE_NODE_MASK (RADIX_TREE_NODE_SIZE - 1)
62 : :
63 : : #define BLOCK_CACHE_NODES_PER_PAGE (1 << (RADIX_TREE_PAGE_SHIFT - RADIX_TREE_NODE_SHIFT))
64 : :
65 : : #define BLOCK_CACHE_MAX_SIZE (10 << 20) /* 100MB cache */
66 : : #define BLOCK_CACHE_REQUESTS (TAPDISK_DATA_REQUESTS << 3)
67 : : #define BLOCK_CACHE_PAGE_IDLETIME 60
68 : :
69 : : typedef struct radix_tree radix_tree_t;
70 : : typedef struct radix_tree_node radix_tree_node_t;
71 : : typedef struct radix_tree_link radix_tree_link_t;
72 : : typedef struct radix_tree_leaf radix_tree_leaf_t;
73 : : typedef struct radix_tree_page radix_tree_page_t;
74 : :
75 : : typedef struct block_cache block_cache_t;
76 : : typedef struct block_cache_request block_cache_request_t;
77 : : typedef struct block_cache_stats block_cache_stats_t;
78 : :
79 : : struct radix_tree_page {
80 : : char *buf;
81 : : size_t size;
82 : : uint64_t sec;
83 : : radix_tree_link_t *owners[BLOCK_CACHE_NODES_PER_PAGE];
84 : : };
85 : :
86 : : struct radix_tree_leaf {
87 : : radix_tree_page_t *page;
88 : : char *buf;
89 : : };
90 : :
91 : : struct radix_tree_link {
92 : : uint32_t time;
93 : : union {
94 : : radix_tree_node_t *next;
95 : : radix_tree_leaf_t leaf;
96 : : } u;
97 : : };
98 : :
99 : : struct radix_tree_node {
100 : : int height;
101 : : radix_tree_link_t links[RADIX_TREE_NODE_SIZE];
102 : : };
103 : :
104 : : struct radix_tree {
105 : : int height;
106 : : uint64_t size;
107 : : uint32_t nodes;
108 : : radix_tree_node_t *root;
109 : :
110 : : block_cache_t *cache;
111 : : };
112 : :
113 : : struct block_cache_request {
114 : : int err;
115 : : char *buf;
116 : : uint64_t secs;
117 : : td_request_t treq;
118 : : block_cache_t *cache;
119 : : };
120 : :
121 : : struct block_cache_stats {
122 : : uint64_t reads;
123 : : uint64_t hits;
124 : : uint64_t misses;
125 : : uint64_t prunes;
126 : : };
127 : :
128 : : struct block_cache {
129 : : int ptype;
130 : : char *name;
131 : :
132 : : uint64_t sectors;
133 : :
134 : : block_cache_request_t requests[BLOCK_CACHE_REQUESTS];
135 : : block_cache_request_t *request_free_list[BLOCK_CACHE_REQUESTS];
136 : : int requests_free;
137 : :
138 : : event_id_t timeout_id;
139 : :
140 : : radix_tree_t tree;
141 : :
142 : : block_cache_stats_t stats;
143 : : };
144 : :
145 : : static inline uint64_t
146 : 0 : radix_tree_calculate_size(int height)
147 : : {
148 : 0 : return (uint64_t)RADIX_TREE_NODE_SIZE <<
149 : 0 : (height * RADIX_TREE_NODE_SHIFT);
150 : : }
151 : :
152 : : static inline int
153 : 0 : radix_tree_calculate_height(uint64_t sectors)
154 : : {
155 : 0 : int height;
156 : 0 : uint64_t tree_size;
157 : :
158 : 0 : height = 1; /* always allocate root node */
159 : 0 : tree_size = radix_tree_calculate_size(height);
160 [ # # ]: 0 : while (sectors > tree_size)
161 : 0 : tree_size = radix_tree_calculate_size(++height);
162 : :
163 : 0 : return height;
164 : : }
165 : :
166 : : static inline int
167 : 0 : radix_tree_index(radix_tree_node_t *node, uint64_t sector)
168 : : {
169 : 0 : return ((sector >> (node->height * RADIX_TREE_NODE_SHIFT)) &
170 : : RADIX_TREE_NODE_MASK);
171 : : }
172 : :
173 : : static inline int
174 : 0 : radix_tree_node_contains_leaves(radix_tree_t *tree, radix_tree_node_t *node)
175 : : {
176 : 0 : return (node->height == 0);
177 : : }
178 : :
179 : : static inline int
180 : 0 : radix_tree_node_is_root(radix_tree_t *tree, radix_tree_node_t *node)
181 : : {
182 : 0 : return (node->height == tree->height);
183 : : }
184 : :
185 : : static inline uint64_t
186 : 0 : radix_tree_size(radix_tree_t *tree)
187 : : {
188 : 0 : return tree->size + tree->nodes * sizeof(radix_tree_node_t);
189 : : }
190 : :
191 : : static inline void
192 : 0 : radix_tree_clear_link(radix_tree_link_t *link)
193 : : {
194 [ # # ]: 0 : if (link)
195 : 0 : memset(link, 0, sizeof(radix_tree_link_t));
196 : 0 : }
197 : :
198 : : static inline radix_tree_node_t *
199 : 0 : radix_tree_allocate_node(radix_tree_t *tree, int height)
200 : : {
201 : 0 : radix_tree_node_t *node;
202 : :
203 : 0 : node = calloc(1, sizeof(radix_tree_node_t));
204 [ # # ]: 0 : if (!node)
205 : : return NULL;
206 : :
207 : 0 : node->height = height;
208 : 0 : tree->nodes++;
209 : :
210 : 0 : return node;
211 : : }
212 : :
213 : : static inline radix_tree_node_t *
214 : 0 : radix_tree_allocate_child_node(radix_tree_t *tree, radix_tree_node_t *parent)
215 : : {
216 : 0 : return radix_tree_allocate_node(tree, parent->height - 1);
217 : : }
218 : :
219 : : void
220 : 0 : radix_tree_free_node(radix_tree_t *tree, radix_tree_node_t *node)
221 : : {
222 [ # # ]: 0 : if (!node)
223 : : return;
224 : :
225 : 0 : free(node);
226 : 0 : tree->nodes--;
227 : : }
228 : :
229 : : static inline radix_tree_page_t *
230 : 0 : radix_tree_allocate_page(radix_tree_t *tree,
231 : : char *buf, uint64_t sec, size_t size)
232 : : {
233 : 0 : radix_tree_page_t *page;
234 : :
235 : 0 : page = calloc(1, sizeof(radix_tree_page_t));
236 [ # # ]: 0 : if (!page)
237 : : return NULL;
238 : :
239 : 0 : page->buf = buf;
240 : 0 : page->sec = sec;
241 : 0 : page->size = size;
242 : 0 : tree->size += size;
243 : :
244 : 0 : return page;
245 : : }
246 : :
247 : : static inline void
248 : 0 : radix_tree_free_page(radix_tree_t *tree, radix_tree_page_t *page)
249 : : {
250 : 0 : int i;
251 : :
252 [ # # ]: 0 : for (i = 0; i < page->size >> RADIX_TREE_NODE_SHIFT; i++)
253 : : DBG("%s: ejecting sector 0x%llx\n",
254 : : tree->cache->name, page->sec + i);
255 : :
256 : 0 : tree->cache->stats.prunes += (page->size >> RADIX_TREE_NODE_SHIFT);
257 : 0 : tree->size -= page->size;
258 : 0 : free(page->buf);
259 : 0 : free(page);
260 : 0 : }
261 : :
262 : : /*
263 : : * remove a leaf and the shared radix_tree_page_t containing its buffer.
264 : : * leaves are deleted, nodes are not; gc will reap the nodes later.
265 : : */
266 : : static void
267 : 0 : radix_tree_remove_page(radix_tree_t *tree, radix_tree_page_t *page)
268 : : {
269 : 0 : int i;
270 : :
271 [ # # ]: 0 : if (!page)
272 : : return;
273 : :
274 [ # # ]: 0 : for (i = 0; i < BLOCK_CACHE_NODES_PER_PAGE; i++)
275 : 0 : radix_tree_clear_link(page->owners[i]);
276 : :
277 : 0 : radix_tree_free_page(tree, page);
278 : : }
279 : :
280 : : static void
281 : 0 : radix_tree_insert_leaf(radix_tree_t *tree, radix_tree_link_t *link,
282 : : radix_tree_page_t *page, off_t off)
283 : : {
284 : 0 : int i;
285 : :
286 [ # # ]: 0 : if (off + RADIX_TREE_NODE_SIZE > page->size)
287 : : return;
288 : :
289 [ # # ]: 0 : for (i = 0; i < BLOCK_CACHE_NODES_PER_PAGE; i++) {
290 [ # # ]: 0 : if (page->owners[i])
291 : 0 : continue;
292 : :
293 : 0 : page->owners[i] = link;
294 : 0 : link->u.leaf.page = page;
295 : 0 : link->u.leaf.buf = page->buf + off;
296 : :
297 : 0 : break;
298 : : }
299 : : }
300 : :
301 : : static char *
302 : 0 : radix_tree_find_leaf(radix_tree_t *tree, uint64_t sector)
303 : : {
304 : 0 : int idx;
305 : 0 : struct timeval now;
306 : 0 : radix_tree_link_t *link;
307 : 0 : radix_tree_node_t *node;
308 : :
309 : 0 : node = tree->root;
310 : 0 : gettimeofday(&now, NULL);
311 : :
312 : 0 : do {
313 : 0 : idx = radix_tree_index(node, sector);
314 : 0 : link = node->links + idx;
315 : 0 : link->time = now.tv_sec;
316 : :
317 [ # # ]: 0 : if (radix_tree_node_contains_leaves(tree, node))
318 : 0 : return link->u.leaf.buf;
319 : :
320 [ # # ]: 0 : if (!link->u.next)
321 : : return NULL;
322 : :
323 : : node = link->u.next;
324 : : } while (1);
325 : : }
326 : :
327 : : static char *
328 : 0 : radix_tree_add_leaf(radix_tree_t *tree, uint64_t sector,
329 : : radix_tree_page_t *page, off_t off)
330 : : {
331 : 0 : int idx;
332 : 0 : struct timeval now;
333 : 0 : radix_tree_link_t *link;
334 : 0 : radix_tree_node_t *node;
335 : :
336 : 0 : node = tree->root;
337 : 0 : gettimeofday(&now, NULL);
338 : :
339 : 0 : do {
340 : 0 : idx = radix_tree_index(node, sector);
341 : 0 : link = node->links + idx;
342 : 0 : link->time = now.tv_sec;
343 : :
344 [ # # ]: 0 : if (radix_tree_node_contains_leaves(tree, node)) {
345 : 0 : radix_tree_remove_page(tree, link->u.leaf.page);
346 : 0 : radix_tree_insert_leaf(tree, link, page, off);
347 : 0 : return link->u.leaf.buf;
348 : : }
349 : :
350 [ # # ]: 0 : if (!link->u.next) {
351 : 0 : link->u.next = radix_tree_allocate_child_node(tree,
352 : : node);
353 [ # # ]: 0 : if (!link->u.next)
354 : : return NULL;
355 : : }
356 : :
357 : 0 : node = link->u.next;
358 : : } while (1);
359 : : }
360 : :
361 : : static int
362 : 0 : radix_tree_add_leaves(radix_tree_t *tree, char *buf,
363 : : uint64_t sector, uint64_t sectors)
364 : : {
365 : 0 : int i;
366 : 0 : radix_tree_page_t *page;
367 : :
368 : 0 : page = radix_tree_allocate_page(tree, buf, sector,
369 : : sectors << RADIX_TREE_NODE_SHIFT);
370 [ # # ]: 0 : if (!page)
371 : : return -ENOMEM;
372 : :
373 [ # # ]: 0 : for (i = 0; i < sectors; i++)
374 [ # # ]: 0 : if (!radix_tree_add_leaf(tree, sector + i,
375 : 0 : page, ((off_t)i << RADIX_TREE_NODE_SHIFT)))
376 : 0 : goto fail;
377 : :
378 : : return 0;
379 : :
380 : 0 : fail:
381 : 0 : page->buf = NULL;
382 : 0 : radix_tree_remove_page(tree, page);
383 : 0 : return -ENOMEM;
384 : : }
385 : :
386 : : static void
387 : 0 : radix_tree_delete_branch(radix_tree_t *tree, radix_tree_node_t *node)
388 : : {
389 : 0 : int i;
390 : 0 : radix_tree_link_t *link;
391 : :
392 [ # # ]: 0 : if (!node)
393 : : return;
394 : :
395 [ # # ]: 0 : for (i = 0; i < RADIX_TREE_NODE_SIZE; i++) {
396 : 0 : link = node->links + i;
397 : :
398 [ # # ]: 0 : if (radix_tree_node_contains_leaves(tree, node))
399 : 0 : radix_tree_remove_page(tree, link->u.leaf.page);
400 : : else
401 : 0 : radix_tree_delete_branch(tree, link->u.next);
402 : :
403 : 0 : radix_tree_clear_link(link);
404 : : }
405 : :
406 : 0 : radix_tree_free_node(tree, node);
407 : : }
408 : :
409 : : static inline void
410 : 0 : radix_tree_destroy(radix_tree_t *tree)
411 : : {
412 : 0 : radix_tree_delete_branch(tree, tree->root);
413 : 0 : tree->root = NULL;
414 : : }
415 : :
416 : : /*
417 : : * returns 1 if @node is empty after pruning, 0 otherwise
418 : : */
419 : : static int
420 : 0 : radix_tree_prune_branch(radix_tree_t *tree,
421 : : radix_tree_node_t *node, uint32_t now)
422 : : {
423 : 0 : int i, empty;
424 : 0 : radix_tree_link_t *link;
425 : :
426 : 0 : empty = 1;
427 [ # # ]: 0 : if (!node)
428 : : return empty;
429 : :
430 [ # # ]: 0 : for (i = 0; i < RADIX_TREE_NODE_SIZE; i++) {
431 : 0 : link = node->links + i;
432 : :
433 [ # # ]: 0 : if (now - link->time < BLOCK_CACHE_PAGE_IDLETIME) {
434 [ # # ]: 0 : if (radix_tree_node_contains_leaves(tree, node)) {
435 : 0 : empty = 0;
436 : 0 : continue;
437 : : }
438 : :
439 [ # # ]: 0 : if (radix_tree_prune_branch(tree, link->u.next, now))
440 : 0 : radix_tree_clear_link(link);
441 : : else
442 : : empty = 0;
443 : :
444 : 0 : continue;
445 : : }
446 : :
447 [ # # ]: 0 : if (radix_tree_node_contains_leaves(tree, node))
448 : 0 : radix_tree_remove_page(tree, link->u.leaf.page);
449 : : else
450 : 0 : radix_tree_delete_branch(tree, link->u.next);
451 : :
452 : 0 : radix_tree_clear_link(link);
453 : : }
454 : :
455 [ # # # # ]: 0 : if (empty && !radix_tree_node_is_root(tree, node))
456 : 0 : radix_tree_free_node(tree, node);
457 : :
458 : : return empty;
459 : : }
460 : :
461 : : /*
462 : : * walk tree and free any node that has been idle for too long
463 : : */
464 : : static void
465 : 0 : radix_tree_prune(radix_tree_t *tree)
466 : : {
467 : 0 : struct timeval now;
468 : :
469 [ # # ]: 0 : if (!tree->root)
470 : 0 : return;
471 : :
472 : 0 : DPRINTF("tree %s has %"PRIu64" bytes\n",
473 : : tree->cache->name, tree->size);
474 : :
475 : 0 : gettimeofday(&now, NULL);
476 : 0 : radix_tree_prune_branch(tree, tree->root, now.tv_sec);
477 : :
478 : 0 : DPRINTF("tree %s now has %"PRIu64" bytes\n",
479 : : tree->cache->name, tree->size);
480 : : }
481 : :
482 : : static inline int
483 : 0 : radix_tree_initialize(radix_tree_t *tree, uint64_t sectors)
484 : : {
485 : 0 : tree->height = radix_tree_calculate_height(sectors);
486 : 0 : tree->root = radix_tree_allocate_node(tree, tree->height);
487 [ # # ]: 0 : if (!tree->root)
488 : 0 : return -ENOMEM;
489 : :
490 : : return 0;
491 : : }
492 : :
493 : : static inline void
494 : 0 : radix_tree_free(radix_tree_t *tree)
495 : : {
496 : 0 : radix_tree_destroy(tree);
497 : : }
498 : :
499 : : static void
500 : 0 : block_cache_prune_event(event_id_t id, char mode, void *private)
501 : : {
502 : 0 : radix_tree_t *tree;
503 : 0 : block_cache_t *cache;
504 : :
505 : 0 : cache = (block_cache_t *)private;
506 : 0 : tree = &cache->tree;
507 : :
508 : 0 : radix_tree_prune(tree);
509 : 0 : }
510 : :
511 : : static inline block_cache_request_t *
512 : 0 : block_cache_get_request(block_cache_t *cache)
513 : : {
514 : 0 : if (!cache->requests_free)
515 : : return NULL;
516 : :
517 : 0 : return cache->request_free_list[--cache->requests_free];
518 : : }
519 : :
520 : : static inline void
521 : 0 : block_cache_put_request(block_cache_t *cache, block_cache_request_t *breq)
522 : : {
523 : 0 : memset(breq, 0, sizeof(block_cache_request_t));
524 : 0 : cache->request_free_list[cache->requests_free++] = breq;
525 : 0 : }
526 : :
527 : : static int
528 : 0 : block_cache_open(td_driver_t *driver, const char *name,
529 : : struct td_vbd_encryption *encryption, td_flag_t flags)
530 : : {
531 : 0 : int i, err;
532 : 0 : radix_tree_t *tree;
533 : 0 : block_cache_t *cache;
534 : :
535 [ # # ]: 0 : if (!td_flag_test(flags, TD_OPEN_RDONLY))
536 : 0 : return -EINVAL;
537 : :
538 [ # # ]: 0 : if (driver->info.sector_size != RADIX_TREE_NODE_SIZE)
539 : : return -EINVAL;
540 : :
541 : 0 : cache = (block_cache_t *)driver->data;
542 : 0 : err = tapdisk_namedup(&cache->name, (char *)name);
543 [ # # ]: 0 : if (err)
544 : : return -ENOMEM;
545 : :
546 : 0 : cache->sectors = driver->info.size;
547 : :
548 : 0 : tree = &cache->tree;
549 : 0 : err = radix_tree_initialize(tree, cache->sectors);
550 [ # # ]: 0 : if (err)
551 : 0 : goto fail;
552 : :
553 : 0 : tree->cache = cache;
554 : 0 : cache->requests_free = BLOCK_CACHE_REQUESTS;
555 [ # # ]: 0 : for (i = 0; i < BLOCK_CACHE_REQUESTS; i++)
556 : 0 : cache->request_free_list[i] = cache->requests + i;
557 : :
558 : 0 : cache->timeout_id = tapdisk_server_register_event(SCHEDULER_POLL_TIMEOUT,
559 : : -1, /* dummy fd */
560 : 0 : TV_SECS(BLOCK_CACHE_PAGE_IDLETIME << 1),
561 : : block_cache_prune_event,
562 : : cache);
563 [ # # ]: 0 : if (cache->timeout_id < 0)
564 : 0 : goto fail;
565 : :
566 : 0 : DPRINTF("opening cache for %s, sectors: %"PRIu64", "
567 : : "tree: %p, height: %d\n",
568 : : cache->name, cache->sectors, tree, tree->height);
569 : :
570 [ # # ]: 0 : if (mlockall(MCL_CURRENT | MCL_FUTURE))
571 : 0 : DPRINTF("mlockall failed: %d\n", -errno);
572 : :
573 : : return 0;
574 : :
575 : 0 : fail:
576 : 0 : free(cache->name);
577 : 0 : radix_tree_free(&cache->tree);
578 : 0 : return err;
579 : : }
580 : :
581 : : static int
582 : 0 : block_cache_close(td_driver_t *driver)
583 : : {
584 : 0 : radix_tree_t *tree;
585 : 0 : block_cache_t *cache;
586 : :
587 : 0 : cache = (block_cache_t *)driver->data;
588 : 0 : tree = &cache->tree;
589 : :
590 : 0 : DPRINTF("closing cache for %s\n", cache->name);
591 : :
592 : 0 : tapdisk_server_unregister_event(cache->timeout_id);
593 : 0 : radix_tree_free(tree);
594 : 0 : free(cache->name);
595 : :
596 : 0 : return 0;
597 : : }
598 : :
599 : : static inline uint64_t
600 : : block_cache_hash(block_cache_t *cache, char *buf)
601 : : {
602 : : return 0;
603 : : #if 0
604 : : int i, n;
605 : : uint64_t cksm, *data;
606 : :
607 : : cksm = 0;
608 : : data = (uint64_t *)buf;
609 : : n = RADIX_TREE_NODE_SIZE / sizeof(uint64_t);
610 : :
611 : : for (i = 0; i < n; i++)
612 : : cksm += data[i];
613 : :
614 : : return ~cksm;
615 : : #endif
616 : : }
617 : :
618 : : static void
619 : 0 : block_cache_hit(block_cache_t *cache, td_request_t treq, char *iov[])
620 : : {
621 : 0 : int i;
622 : 0 : off_t off;
623 : :
624 : 0 : cache->stats.hits += treq.secs;
625 : :
626 [ # # ]: 0 : for (i = 0; i < treq.secs; i++) {
627 : 0 : DBG("%s: block cache hit: sec 0x%08llx, hash: 0x%08llx\n",
628 : : cache->name, treq.sec + i, block_cache_hash(cache, iov[i]));
629 : :
630 : 0 : off = (off_t)i << RADIX_TREE_NODE_SHIFT;
631 : 0 : memcpy(treq.buf + off, iov[i], RADIX_TREE_NODE_SIZE);
632 : : }
633 : :
634 : 0 : td_complete_request(treq, 0);
635 : 0 : }
636 : :
637 : : static void
638 : 0 : block_cache_populate_cache(td_request_t clone, int err)
639 : : {
640 : 0 : int i;
641 : 0 : radix_tree_t *tree;
642 : 0 : block_cache_t *cache;
643 : 0 : block_cache_request_t *breq;
644 : :
645 : 0 : breq = (block_cache_request_t *)clone.cb_data;
646 : 0 : cache = breq->cache;
647 : 0 : tree = &cache->tree;
648 : 0 : breq->secs -= clone.secs;
649 [ # # ]: 0 : breq->err = (breq->err ? breq->err : err);
650 : :
651 [ # # ]: 0 : if (breq->secs)
652 : : return;
653 : :
654 [ # # ]: 0 : if (breq->err) {
655 : 0 : free(breq->buf);
656 : 0 : goto out;
657 : : }
658 : :
659 [ # # ]: 0 : for (i = 0; i < breq->treq.secs; i++) {
660 : 0 : off_t off = (off_t)i << RADIX_TREE_NODE_SHIFT;
661 : 0 : DBG("%s: populating sec 0x%08llx\n",
662 : : cache->name, breq->treq.sec + i);
663 : 0 : memcpy(breq->treq.buf + off,
664 : 0 : breq->buf + off, RADIX_TREE_NODE_SIZE);
665 : : }
666 : :
667 [ # # ]: 0 : if (radix_tree_add_leaves(tree, breq->buf,
668 : : breq->treq.sec, breq->treq.secs))
669 : 0 : free(breq->buf);
670 : :
671 : 0 : out:
672 : 0 : td_complete_request(breq->treq, breq->err);
673 : 0 : block_cache_put_request(cache, breq);
674 : : }
675 : :
676 : : static void
677 : 0 : block_cache_miss(block_cache_t *cache, td_request_t treq)
678 : : {
679 : 0 : void *buf;
680 : 0 : size_t size;
681 : 0 : td_request_t clone;
682 : 0 : radix_tree_t *tree;
683 : 0 : block_cache_request_t *breq;
684 : :
685 : 0 : DBG("%s: block cache miss: sec 0x%08llx\n", cache->name, treq.sec);
686 : :
687 : 0 : clone = treq;
688 : 0 : tree = &cache->tree;
689 : 0 : size = (size_t)treq.secs << RADIX_TREE_NODE_SHIFT;
690 : :
691 : 0 : cache->stats.misses += treq.secs;
692 : :
693 [ # # ]: 0 : if (radix_tree_size(tree) + size >= BLOCK_CACHE_MAX_SIZE)
694 : 0 : goto out;
695 : :
696 [ # # ]: 0 : breq = block_cache_get_request(cache);
697 [ # # ]: 0 : if (!breq)
698 : 0 : goto out;
699 : :
700 [ # # ]: 0 : if (posix_memalign(&buf, RADIX_TREE_NODE_SIZE, size)) {
701 : 0 : block_cache_put_request(cache, breq);
702 : 0 : goto out;
703 : : }
704 : :
705 : 0 : breq->treq = treq;
706 : 0 : breq->secs = treq.secs;
707 : 0 : breq->err = 0;
708 : 0 : breq->buf = buf;
709 : 0 : breq->cache = cache;
710 : :
711 : 0 : clone.buf = buf;
712 : 0 : clone.cb = block_cache_populate_cache;
713 : 0 : clone.cb_data = breq;
714 : :
715 : 0 : out:
716 : 0 : td_forward_request(clone);
717 : 0 : }
718 : :
719 : : static void
720 : 0 : block_cache_queue_read(td_driver_t *driver, td_request_t treq)
721 : : {
722 : 0 : int i;
723 : 0 : radix_tree_t *tree;
724 : 0 : block_cache_t *cache;
725 : 0 : char *iov[BLOCK_CACHE_NODES_PER_PAGE];
726 : :
727 : 0 : cache = (block_cache_t *)driver->data;
728 : 0 : tree = &cache->tree;
729 : :
730 : 0 : cache->stats.reads += treq.secs;
731 : :
732 [ # # ]: 0 : if (treq.secs > BLOCK_CACHE_NODES_PER_PAGE)
733 : 0 : return td_forward_request(treq);
734 : :
735 [ # # ]: 0 : for (i = 0; i < treq.secs; i++) {
736 : 0 : iov[i] = radix_tree_find_leaf(tree, treq.sec + i);
737 [ # # ]: 0 : if (!iov[i])
738 : 0 : return block_cache_miss(cache, treq);
739 : : }
740 : :
741 : 0 : return block_cache_hit(cache, treq, iov);
742 : : }
743 : :
744 : : static void
745 : 0 : block_cache_queue_write(td_driver_t *driver, td_request_t treq)
746 : : {
747 : 0 : td_complete_request(treq, -EPERM);
748 : 0 : }
749 : :
750 : : static int
751 : 0 : block_cache_get_parent_id(td_driver_t *driver, td_disk_id_t *id)
752 : : {
753 : 0 : return -EINVAL;
754 : : }
755 : :
756 : : static int
757 : 0 : block_cache_validate_parent(td_driver_t *driver,
758 : : td_driver_t *pdriver, td_flag_t flags)
759 : : {
760 [ # # ]: 0 : if (!td_flag_test(pdriver->state, TD_DRIVER_RDONLY))
761 : : return -EINVAL;
762 : :
763 [ # # ]: 0 : if (strcmp(driver->name, pdriver->name))
764 : 0 : return -EINVAL;
765 : :
766 : : return 0;
767 : : }
768 : :
769 : : static void
770 : 0 : block_cache_debug(td_driver_t *driver)
771 : : {
772 : 0 : block_cache_t *cache;
773 : 0 : block_cache_stats_t *stats;
774 : :
775 : 0 : cache = (block_cache_t *)driver->data;
776 : 0 : stats = &cache->stats;
777 : :
778 : 0 : WARN("BLOCK CACHE %s\n", cache->name);
779 : 0 : WARN("reads: %"PRIu64", hits: %"PRIu64", "
780 : : "misses: %"PRIu64", prunes: %"PRIu64"\n",
781 : : stats->reads, stats->hits, stats->misses, stats->prunes);
782 : 0 : }
783 : :
784 : : struct tap_disk tapdisk_block_cache = {
785 : : .disk_type = "tapdisk_block_cache",
786 : : .flags = 0,
787 : : .private_data_size = sizeof(block_cache_t),
788 : : .td_open = block_cache_open,
789 : : .td_close = block_cache_close,
790 : : .td_queue_read = block_cache_queue_read,
791 : : .td_queue_write = block_cache_queue_write,
792 : : .td_get_parent_id = block_cache_get_parent_id,
793 : : .td_validate_parent = block_cache_validate_parent,
794 : : .td_debug = block_cache_debug,
795 : : };
|
