dedup

data deduplication program
git clone git://git.2f30.org/dedup.git
Log | Files | Refs | README | LICENSE

icache.c (1928B)


      1 #include <sys/types.h>
      2 
      3 #include <err.h>
      4 #include <stdint.h>
      5 #include <stdlib.h>
      6 #include <string.h>
      7 
      8 #include "blake2.h"
      9 #include "dedup.h"
     10 #include "tree.h"
     11 
     12 struct node {
     13 	struct blk_desc desc;
     14 	RB_ENTRY(node) e;
     15 };
     16 RB_HEAD(icache_head, node);
     17 
     18 struct icache {
     19 	struct icache_head nodes;
     20 	unsigned long long hits;
     21 	unsigned long long misses;
     22 };
     23 
     24 static int
     25 node_cmp(struct node *e1, struct node *e2)
     26 {
     27 	int r;
     28 
     29 	r = memcmp(e1->desc.md, e2->desc.md, sizeof(e1->desc.md));
     30 	if (r > 0)
     31 		return 1;
     32 	else if (r < 0)
     33 		return -1;
     34 	return 0;
     35 }
     36 static RB_PROTOTYPE(icache_head, node, e, node_cmp);
     37 static RB_GENERATE(icache_head, node, e, node_cmp);
     38 
     39 static struct node *
     40 alloc_node(struct blk_desc *desc)
     41 {
     42 	struct node *node;
     43 
     44 	node = calloc(1, sizeof(*node));
     45 	if (node == NULL)
     46 		err(1, "calloc");
     47 	node->desc = *desc;
     48 	return node;
     49 }
     50 
     51 static void
     52 free_node(struct node *node)
     53 {
     54 	free(node);
     55 }
     56 
     57 struct icache *
     58 alloc_icache(void)
     59 {
     60 	struct icache *icache;
     61 
     62 	icache = calloc(1, sizeof(*icache));
     63 	if (icache == NULL)
     64 		err(1, "calloc");
     65 	RB_INIT(&icache->nodes);
     66 	return icache;
     67 }
     68 
     69 void
     70 free_icache(struct icache *icache)
     71 {
     72 	struct node *node, *tmp;
     73 
     74 	RB_FOREACH_SAFE(node, icache_head, &icache->nodes, tmp) {
     75 		RB_REMOVE(icache_head, &icache->nodes, node);
     76 		free_node(node);
     77 	}
     78 	free(icache);
     79 }
     80 
     81 void
     82 insert_icache(struct icache *icache, struct blk_desc *desc)
     83 {
     84 	struct node *node;
     85 
     86 	node = alloc_node(desc);
     87 	if (RB_INSERT(icache_head, &icache->nodes, node) != NULL)
     88 		free_node(node);
     89 }
     90 
     91 int
     92 lookup_icache(struct icache *icache, struct blk_desc *desc)
     93 {
     94 	struct node *node, key;
     95 
     96 	key.desc = *desc;
     97 	node = RB_FIND(icache_head, &icache->nodes, &key);
     98 	if (node != NULL) {
     99 		icache->hits++;
    100 		*desc = node->desc;
    101 		return 0;
    102 	}
    103 	icache->misses++;
    104 	return -1;
    105 }
    106 
    107 void
    108 icache_stats(struct icache *icache, unsigned long long *hits,
    109              unsigned long long *misses)
    110 {
    111 	*hits = icache->hits;
    112 	*misses = icache->misses;
    113 }
    114