diff options
author | Christian Grothoff <christian@grothoff.org> | 2017-02-20 15:09:00 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2017-02-20 15:09:19 +0100 |
commit | a3882b58f1c5976677aa65b0af8a48e8e946b06e (patch) | |
tree | bd841d8e78052a05821e194d002ca843693fb2c9 /src/block/bg_bf.c | |
parent | f0149c5430f42a8bad422e9c51754af59c7bfa2f (diff) | |
download | gnunet-a3882b58f1c5976677aa65b0af8a48e8e946b06e.tar.gz gnunet-a3882b58f1c5976677aa65b0af8a48e8e946b06e.zip |
first half of new BLOCK API to generalize duplicate detection beyond BFs
Diffstat (limited to 'src/block/bg_bf.c')
-rw-r--r-- | src/block/bg_bf.c | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c new file mode 100644 index 000000000..f03ae5247 --- /dev/null +++ b/src/block/bg_bf.c | |||
@@ -0,0 +1,173 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | Copyright (C) 2017 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | ||
18 | Boston, MA 02110-1301, USA. | ||
19 | */ | ||
20 | /** | ||
21 | * @file block/bg_bf.c | ||
22 | * @brief implementation of a block group using a Bloom filter | ||
23 | * to drop duplicate blocks | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "gnunet_block_group_lib.h" | ||
29 | #include "gnunet_block_plugin.h" | ||
30 | |||
31 | |||
32 | /** | ||
33 | * Internal data structure for a block group. | ||
34 | */ | ||
35 | struct BfGroupInternals | ||
36 | { | ||
37 | /** | ||
38 | * A Bloom filter to weed out duplicate replies probabilistically. | ||
39 | */ | ||
40 | struct GNUNET_CONTAINER_BloomFilter *bf; | ||
41 | |||
42 | /** | ||
43 | * Set from the nonce to mingle the hashes before going into the @e bf. | ||
44 | */ | ||
45 | uint32_t bf_mutator; | ||
46 | |||
47 | /** | ||
48 | * Size of @a bf. | ||
49 | */ | ||
50 | uint32_t bf_size; | ||
51 | |||
52 | }; | ||
53 | |||
54 | |||
55 | /** | ||
56 | * Serialize state of a block group. | ||
57 | * | ||
58 | * @param bg group to serialize | ||
59 | * @param[out] raw_data set to the serialized state | ||
60 | * @param[out] raw_data_size set to the number of bytes in @a raw_data | ||
61 | * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not | ||
62 | * supported, #GNUNET_SYSERR on error | ||
63 | */ | ||
64 | static int | ||
65 | bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg, | ||
66 | void **raw_data, | ||
67 | size_t *raw_data_size) | ||
68 | { | ||
69 | struct BfGroupInternals *gi = bg->internal_cls; | ||
70 | char *raw; | ||
71 | |||
72 | raw = GNUNET_malloc (gi->bf_size); | ||
73 | if (GNUNET_OK != | ||
74 | GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf, | ||
75 | raw, | ||
76 | gi->bf_size)) | ||
77 | { | ||
78 | GNUNET_break (0); | ||
79 | return GNUNET_SYSERR; | ||
80 | } | ||
81 | *raw_data = raw; | ||
82 | *raw_data_size = gi->bf_size; | ||
83 | return GNUNET_OK; | ||
84 | } | ||
85 | |||
86 | |||
87 | /** | ||
88 | * Destroy resources used by a block group. | ||
89 | * | ||
90 | * @param bg group to destroy, NULL is allowed | ||
91 | */ | ||
92 | static void | ||
93 | bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg) | ||
94 | { | ||
95 | struct BfGroupInternals *gi = bg->internal_cls; | ||
96 | |||
97 | GNUNET_CONTAINER_bloomfilter_free (gi->bf); | ||
98 | GNUNET_free (gi); | ||
99 | GNUNET_free (bg); | ||
100 | } | ||
101 | |||
102 | |||
103 | /** | ||
104 | * Create a new block group that filters duplicates using a Bloom filter. | ||
105 | * | ||
106 | * @param ctx block context in which the block group is created | ||
107 | * @param bf_size size of the Bloom filter | ||
108 | * @param bf_k K-value for the Bloom filter | ||
109 | * @param type block type | ||
110 | * @param nonce random value used to seed the group creation | ||
111 | * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh | ||
112 | * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh | ||
113 | * @return block group handle, NULL if block groups are not supported | ||
114 | * by this @a type of block (this is not an error) | ||
115 | */ | ||
116 | struct GNUNET_BLOCK_Group * | ||
117 | GNUNET_BLOCK_GROUP_bf_create (void *cls, | ||
118 | size_t bf_size, | ||
119 | unsigned int bf_k, | ||
120 | enum GNUNET_BLOCK_Type type, | ||
121 | uint32_t nonce, | ||
122 | const void *raw_data, | ||
123 | size_t raw_data_size) | ||
124 | { | ||
125 | struct BfGroupInternals *gi; | ||
126 | struct GNUNET_BLOCK_Group *bg; | ||
127 | |||
128 | gi = GNUNET_new (struct BfGroupInternals); | ||
129 | gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? NULL : raw_data, | ||
130 | bf_size, | ||
131 | bf_k); | ||
132 | gi->bf_mutator = nonce; | ||
133 | gi->bf_size = bf_size; | ||
134 | bg = GNUNET_new (struct GNUNET_BLOCK_Group); | ||
135 | bg->type = type; | ||
136 | bg->serialize_cb = &bf_group_serialize_cb; | ||
137 | bg->destroy_cb = &bf_group_destroy_cb; | ||
138 | bg->internal_cls = gi; | ||
139 | return bg; | ||
140 | } | ||
141 | |||
142 | |||
143 | /** | ||
144 | * Test if @a hc is contained in the Bloom filter of @a bg. If so, | ||
145 | * return #GNUNET_YES. If not, add @a hc to the Bloom filter and | ||
146 | * return #GNUNET_NO. | ||
147 | * | ||
148 | * @param bg block group to use for testing | ||
149 | * @param hc hash of element to evaluate | ||
150 | * @return #GNUNET_YES if @a hc is (likely) a duplicate | ||
151 | * #GNUNET_NO if @a hc was definitively not in @bg (but now is) | ||
152 | */ | ||
153 | int | ||
154 | GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, | ||
155 | const struct GNUNET_HashCode *hc) | ||
156 | { | ||
157 | struct BfGroupInternals *gi = bg->internal_cls; | ||
158 | struct GNUNET_HashCode mhash; | ||
159 | |||
160 | GNUNET_BLOCK_mingle_hash (hc, | ||
161 | gi->bf_mutator, | ||
162 | &mhash); | ||
163 | if (GNUNET_YES == | ||
164 | GNUNET_CONTAINER_bloomfilter_test (gi->bf, | ||
165 | &mhash)) | ||
166 | return GNUNET_YES; | ||
167 | GNUNET_CONTAINER_bloomfilter_add (gi->bf, | ||
168 | &mhash); | ||
169 | return GNUNET_NO; | ||
170 | } | ||
171 | |||
172 | |||
173 | /* end of bg_bf.c */ | ||