1 /*
2 * Copyright (c) 2012, 2021 by Farsight Security, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "dnstable-private.h"
18
19 /*
20 * Given two sorted arrays each of which has no duplicates,
21 * return a sorted output array with duplicates removed.
22 * Effectively, a union of two sorted sets.
23 *
24 * Returns the number of values in output, limited to max_output values
25 * (excess values will be silently ignored).
26 */
27 static int
sorted_merge_dedup(uint16_t * input1,int n_input1,uint16_t * input2,int n_input2,uint16_t * output,int max_output)28 sorted_merge_dedup(uint16_t *input1, int n_input1, uint16_t *input2, int n_input2, uint16_t *output, int max_output)
29 {
30 uint16_t *orig_output = output;
31
32 while (n_input1 > 0 || n_input2 > 0) {
33 bool take_input1 = false;
34 bool take_input2 = false;
35
36 if (output - orig_output >= max_output)
37 break; /* hit max; silently ignore any remaining values from inputs 1 or 2 */
38 else if (n_input1 == 0 || (n_input2 > 0 && *input1 > *input2))
39 take_input2 = true;
40 else if (n_input2 == 0 || (n_input1 > 0 && *input1 < *input2))
41 take_input1 = true;
42 else /* equal values, remove from both arrays */
43 take_input1 = take_input2 = true;
44
45 if (take_input1) {
46 *output = *input1++;
47 n_input1--;
48 }
49 if (take_input2) {
50 *output = *input2++;
51 n_input2--;
52 }
53 output++;
54 }
55
56 return output - orig_output;
57 }
58
59
60 /*
61 * During a merge of either RRSET_NAME_FWD or RDATA_NAME_REV entries,
62 * if entry 1 has a non-empty rrtype bitmap and entry 2 has an empty
63 * rrtype bitmap, the merge will be an empty bitmap.
64 *
65 * The logic is because merging "I only index these rrtypes" with "I
66 * have no rrtype info: it could be any rrtype", the result should
67 * reflect "it could be any rrtype".
68 *
69 * Note that to indicate an empty bitmap: we have to malloc a
70 * non-empty value but return the length of the value as zero.
71 * Otherwise, *len_merged_val should be equal to the size of the
72 * malloced value we return.
73 */
74 static uint8_t *
merge_rrtype_bitmaps(const uint8_t * val0,size_t len_val0,const uint8_t * val1,size_t len_val1,size_t * len_merged_val)75 merge_rrtype_bitmaps(const uint8_t *val0, size_t len_val0,
76 const uint8_t *val1, size_t len_val1,
77 size_t *len_merged_val)
78 {
79 uint8_t *res;
80 rrtype_unpacked_set rrtype_set_1, rrtype_set_2, rrtype_set_merged;
81 int count_rrtypes = 0, n_rrtypes1 = 0, n_rrtypes2 = 0;
82
83 if (len_val0 == 0 || len_val1 == 0) {
84 *len_merged_val = 0;
85 res = my_malloc(1);
86 *res = 0; /* won't be used, but at least initialize it */
87 return res;
88 } else if (len_val0 == len_val1 && !memcmp(val0, val1, len_val0)) { /* identical values */
89 *len_merged_val = len_val0;
90 res = my_malloc(*len_merged_val);
91 memcpy(res, val0, *len_merged_val);
92 return res;
93 } else if (len_val0 == 1 && len_val1 == 1) {
94 rrtype_set_1.rrtypes[0] = (uint16_t)*val0;
95 rrtype_set_2.rrtypes[0] = (uint16_t)*val1;
96 n_rrtypes1 = 1;
97 n_rrtypes2 = 1;
98 } else if (len_val0 == 2 && len_val1 == 2) {
99 rrtype_set_1.rrtypes[0] = (uint16_t)le16toh(*(uint16_t*)val0);
100 rrtype_set_2.rrtypes[0] = (uint16_t)le16toh(*(uint16_t*)val1);
101 n_rrtypes1 = 1;
102 n_rrtypes2 = 1;
103 } else {
104 /* unpack both sides as possibly bitmaps, but they could be len 1 or 2 anyway. */
105 n_rrtypes1 = rrtype_union_unpack(val0, len_val0, &rrtype_set_1);
106 if (n_rrtypes1 == -1)
107 return NULL; /* failed -- corrupt union or too many to unpack */
108
109 n_rrtypes2 = rrtype_union_unpack(val1, len_val1, &rrtype_set_2);
110 if (n_rrtypes2 == -1)
111 return NULL; /* failed -- corrupt union or too many to unpack */
112 }
113
114 count_rrtypes = sorted_merge_dedup(rrtype_set_1.rrtypes, n_rrtypes1,
115 rrtype_set_2.rrtypes, n_rrtypes2,
116 rrtype_set_merged.rrtypes, MAX_RRTYPES_MAPPABLE);
117
118 /* now form a new bitmap union */
119 uint8_t bitmap[32]; /* 256 bits / 8 bits per byte */
120 memset(bitmap, 0, sizeof(bitmap));
121 uint8_t window_block = 0;
122 uint8_t bitmap_len = 0;
123 uint8_t result_data[65536 / 8];
124 uint16_t result_index = 0;
125
126 for (int n = 0; n < count_rrtypes; n++) {
127 uint16_t my_rrtype = rrtype_set_merged.rrtypes[n];
128 uint8_t cur_window = my_rrtype / 256;
129
130 if (cur_window != window_block) {
131 /* Per RFC6840, do not write out an empty bitmap */
132 if (bitmap_len > 0) {
133 assert((result_index + sizeof(window_block) + sizeof(bitmap_len) + bitmap_len)
134 < sizeof(result_data)/sizeof(&result_data[0]));
135
136 memcpy(&result_data[result_index], (const uint8_t*)&window_block,
137 sizeof(window_block));
138 result_index += sizeof(window_block);
139
140 memcpy(&result_data[result_index], (const uint8_t*)&bitmap_len,
141 sizeof(bitmap_len));
142 result_index += sizeof(bitmap_len);
143
144 memcpy(&result_data[result_index], (const uint8_t*)bitmap, bitmap_len);
145 result_index += bitmap_len;
146
147 bitmap_len = 0;
148 }
149 memset(bitmap, 0, sizeof(bitmap));
150 window_block = cur_window;
151 }
152
153 uint8_t offset = my_rrtype % 256;
154 uint8_t byte = offset / 8;
155 uint8_t bit = offset % 8;
156
157 bitmap[byte] |= 0x80 >> bit;
158 bitmap_len = 1 + byte;
159 }
160
161 if (bitmap_len != 0) {
162 assert((result_index + sizeof(window_block) + sizeof(bitmap_len) + bitmap_len)
163 < sizeof(result_data)/sizeof(&result_data[0]));
164
165 memcpy(&result_data[result_index], (const uint8_t*)&window_block, sizeof(window_block));
166 result_index += sizeof(window_block);
167
168 memcpy(&result_data[result_index], (const uint8_t*)&bitmap_len, sizeof(bitmap_len));
169 result_index += sizeof(bitmap_len);
170
171 memcpy(&result_data[result_index], (const uint8_t*)bitmap, bitmap_len);
172 result_index += bitmap_len;
173 }
174
175 *len_merged_val = result_index;
176 res = my_malloc(*len_merged_val);
177 memcpy(res, result_data, *len_merged_val);
178
179 return res;
180 }
181
182 void
dnstable_merge_func(void * clos,const uint8_t * key,size_t len_key,const uint8_t * val0,size_t len_val0,const uint8_t * val1,size_t len_val1,uint8_t ** merged_val,size_t * len_merged_val)183 dnstable_merge_func(void *clos,
184 const uint8_t *key, size_t len_key,
185 const uint8_t *val0, size_t len_val0,
186 const uint8_t *val1, size_t len_val1,
187 uint8_t **merged_val, size_t *len_merged_val)
188 {
189 uint64_t time_first0, time_last0, count0;
190 uint64_t time_first1, time_last1, count1;
191
192 if (len_key && (key[0] == ENTRY_TYPE_RRSET ||
193 key[0] == ENTRY_TYPE_RDATA))
194 {
195 assert(len_val0 && len_val1);
196 dnstable_res res;
197
198 res = triplet_unpack(val0, len_val0, &time_first0, &time_last0, &count0);
199 assert(res == dnstable_res_success);
200 res = triplet_unpack(val1, len_val1, &time_first1, &time_last1, &count1);
201 assert(res == dnstable_res_success);
202
203 time_first0 = (time_first0 < time_first1) ? time_first0 : time_first1;
204 time_last0 = (time_last0 > time_last1) ? time_last0 : time_last1;
205 count0 += count1;
206
207 *merged_val = my_malloc(32);
208 *len_merged_val = triplet_pack(*merged_val, time_first0, time_last0, count0);
209 } else if (len_key && (key[0] == ENTRY_TYPE_RRSET_NAME_FWD ||
210 key[0] == ENTRY_TYPE_RDATA_NAME_REV)) {
211 *merged_val = merge_rrtype_bitmaps(val0, len_val0, val1, len_val1, len_merged_val);
212 } else if (len_key == 1 && (key[0] == ENTRY_TYPE_TIME_RANGE)) {
213 dnstable_res res;
214
215 if ((len_val0 == 0) || (len_val1 == 0)) {
216 *merged_val = my_malloc(1);
217 *len_merged_val = 0;
218 return;
219 }
220
221 res = pair_unpack(val0, len_val0, &time_first0, &time_last0);
222 assert(res == dnstable_res_success);
223 res = pair_unpack(val1, len_val1, &time_first1, &time_last1);
224 assert(res == dnstable_res_success);
225 time_first0 = (time_first0 < time_first1) ? time_first0 : time_first1;
226 time_last0 = (time_last0 > time_last1) ? time_last0 : time_last1;
227 *merged_val = my_malloc(32);
228 *len_merged_val = pair_pack(*merged_val, time_first0, time_last0);
229 } else if (len_key == 2 && (key[0] == ENTRY_TYPE_VERSION)) {
230 uint32_t vers0, vers1, minvers;
231 size_t len;
232
233 /*
234 * A zero-length value for a version entry indicates that the
235 * entry has been processed by a pre-versioning version of the
236 * dnstable merge function, or by a version of the dnstable
237 * merge function which does not support the version entry's
238 * type. In either case, we make the merged version value
239 * empty to preserve this indication.
240 */
241 if ((len_val0 == 0) || (len_val1 == 0)) {
242 *merged_val = my_calloc(1,1);
243 *len_merged_val = 0;
244 return;
245 }
246
247 switch(key[1]) {
248 case ENTRY_TYPE_RRSET:
249 case ENTRY_TYPE_RRSET_NAME_FWD:
250 case ENTRY_TYPE_RDATA:
251 case ENTRY_TYPE_RDATA_NAME_REV:
252 break;
253 default:
254 *merged_val = my_calloc(1,1);
255 *len_merged_val = 0;
256 return;
257 }
258
259 len = mtbl_varint_decode32(val0, &vers0);
260 assert(len == len_val0);
261 len = mtbl_varint_decode32(val1, &vers1);
262 assert(len == len_val1);
263 minvers = (vers0 < vers1)?vers0:vers1;
264
265 *len_merged_val = mtbl_varint_length(minvers);
266 *merged_val = my_calloc(1, *len_merged_val);
267 mtbl_varint_encode32(*merged_val, minvers);
268 } else {
269 *merged_val = my_calloc(1, 1);
270 *len_merged_val = 0;
271 }
272 }
273