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 <stdlib.h>
19 : : #include <string.h>
20 : : #include <assert.h>
21 : : #include <stdint.h>
22 : :
23 : : #include "common.h"
24 : : #include "avltree.h"
25 : : #include "snapshot.h"
26 : :
27 : : #include "memleak.h"
28 : :
29 : : #ifdef __DEBUG
30 : : #ifndef __DEBUG_SNAP
31 : : #undef DBG
32 : : #undef DBGCMD
33 : : #undef DBGSW
34 : : #define DBG(...)
35 : : #define DBGCMD(...)
36 : : #define DBGSW(n, ...)
37 : : #endif
38 : : #endif
39 : :
40 : : // lexicographically compares two variable-length binary streams
41 : 1928 : int _snp_keycmp(void *key1, size_t keylen1, void *key2, size_t keylen2)
42 : : {
43 [ + + ]: 1928 : if (keylen1 == keylen2) {
44 : 1926 : return memcmp(key1, key2, keylen1);
45 : : }else {
46 [ + - ]: 2 : size_t len = MIN(keylen1, keylen2);
47 : 2 : int cmp = memcmp(key1, key2, len);
48 [ + - ]: 2 : if (cmp != 0) return cmp;
49 : : else {
50 : 1928 : return (int)((int)keylen1 - (int)keylen2);
51 : : }
52 : : }
53 : : }
54 : :
55 : 1407 : int _snp_seqnum_cmp(struct avl_node *a, struct avl_node *b, void *aux)
56 : : {
57 : : struct snap_wal_entry *aa, *bb;
58 : 1407 : aa = _get_entry(a, struct snap_wal_entry, avl_seq);
59 : 1407 : bb = _get_entry(b, struct snap_wal_entry, avl_seq);
60 : 1407 : return (aa->seqnum - bb->seqnum);
61 : : }
62 : :
63 : 3753 : int _snp_wal_cmp(struct avl_node *a, struct avl_node *b, void *aux)
64 : : {
65 : 3753 : struct _fdb_key_cmp_info *info = (struct _fdb_key_cmp_info*)aux;
66 : : struct snap_wal_entry *aa, *bb;
67 : 3753 : aa = _get_entry(a, struct snap_wal_entry, avl);
68 : 3753 : bb = _get_entry(b, struct snap_wal_entry, avl);
69 : :
70 [ + + ]: 3753 : if (info->kvs_config.custom_cmp) {
71 : : // custom compare function for variable-length key
72 [ + - ]: 1825 : if (info->kvs) {
73 : : // multi KV instance mode
74 : : // KV ID should be compared separately
75 : 1825 : size_t size_id = sizeof(fdb_kvs_id_t);
76 : : fdb_kvs_id_t a_id, b_id, _a_id, _b_id;
77 : 1825 : _a_id = *(fdb_kvs_id_t*)aa->key;
78 : 1825 : _b_id = *(fdb_kvs_id_t*)bb->key;
79 : 1825 : a_id = _endian_decode(_a_id);
80 : 1825 : b_id = _endian_decode(_b_id);
81 : :
82 [ - + ]: 1825 : if (a_id < b_id) {
83 : 0 : return -1;
84 [ - + ]: 1825 : } else if (a_id > b_id) {
85 : 0 : return 1;
86 : : } else {
87 : : return info->kvs_config.custom_cmp(
88 : 1825 : (uint8_t*)aa->key + size_id, aa->keylen - size_id,
89 : 1825 : (uint8_t*)bb->key + size_id, bb->keylen - size_id);
90 : : }
91 : : } else {
92 : : return info->kvs_config.custom_cmp(aa->key, aa->keylen,
93 : 0 : bb->key, bb->keylen);
94 : : }
95 : : } else {
96 : 3753 : return _snp_keycmp(aa->key, aa->keylen, bb->key, bb->keylen);
97 : : }
98 : : }
99 : :
100 : :
101 : 33 : fdb_status snap_init(struct snap_handle *shandle, fdb_kvs_handle *handle)
102 : : {
103 : 33 : shandle->key_tree = (struct avl_tree *) malloc(sizeof(struct avl_tree));
104 [ - + ]: 33 : if (!shandle->key_tree) {
105 : 0 : return FDB_RESULT_ALLOC_FAIL;
106 : : }
107 : 33 : shandle->cmp_info.kvs_config = handle->kvs_config;
108 : 33 : shandle->cmp_info.kvs = handle->kvs;
109 : :
110 : 33 : avl_init(shandle->key_tree, (void *)&shandle->cmp_info);
111 : 33 : shandle->seq_tree = (struct avl_tree *) malloc(sizeof(struct avl_tree));
112 [ - + ]: 33 : if (!shandle->seq_tree) {
113 : 0 : return FDB_RESULT_ALLOC_FAIL;
114 : : }
115 : 33 : avl_init(shandle->seq_tree, NULL);
116 : 33 : spin_init(&shandle->lock);
117 : 33 : shandle->ref_cnt = 1;
118 : 33 : return FDB_RESULT_SUCCESS;
119 : : }
120 : :
121 : 227 : fdb_status snap_insert(struct snap_handle *shandle, fdb_doc *doc,
122 : : uint64_t offset)
123 : : {
124 : : struct snap_wal_entry query;
125 : : struct snap_wal_entry *item;
126 : : struct avl_node *node;
127 : 227 : memset(&query, 0, sizeof(snap_wal_entry));
128 : 227 : query.key = doc->key;
129 : 227 : query.keylen = doc->keylen;
130 : 227 : node = avl_search(shandle->key_tree, &query.avl, _snp_wal_cmp);
131 : :
132 [ + + ]: 227 : if (!node) {
133 : 225 : item = (struct snap_wal_entry *) malloc(sizeof(struct snap_wal_entry));
134 : 225 : item->keylen = doc->keylen;
135 : 225 : item->key = doc->key;
136 : 225 : item->seqnum = doc->seqnum;
137 [ - + ]: 225 : item->action = doc->deleted ? WAL_ACT_LOGICAL_REMOVE : WAL_ACT_INSERT;
138 : 225 : item->offset = offset;
139 : 225 : item->flag = 0;
140 : 225 : avl_insert(shandle->key_tree, &item->avl, _snp_wal_cmp);
141 : 225 : avl_insert(shandle->seq_tree, &item->avl_seq, _snp_seqnum_cmp);
142 : :
143 : : // Note: same logic in wal_commit
144 : 225 : shandle->stat.wal_ndocs++;
145 [ - + ]: 225 : if (doc->deleted) {
146 : 0 : shandle->stat.wal_ndeletes++;
147 : : }
148 : : } else {
149 : : // replace existing node with new values so there are no duplicates
150 : 2 : item = _get_entry(node, struct snap_wal_entry, avl);
151 : 2 : free(item->key);
152 : 2 : item->keylen = doc->keylen;
153 : 2 : item->key = doc->key;
154 [ + - ]: 2 : if (item->seqnum != doc->seqnum) { // Re-index duplicate into seqtree
155 : 2 : item->seqnum = doc->seqnum;
156 : 2 : avl_remove(shandle->seq_tree, &item->avl_seq);
157 : 2 : avl_insert(shandle->seq_tree, &item->avl_seq, _snp_seqnum_cmp);
158 : : }
159 : :
160 : : // Note: same logic in wal_commit
161 [ + - ][ - + ]: 2 : if (item->action == WAL_ACT_INSERT &&
162 : : doc->deleted) {
163 : 0 : shandle->stat.wal_ndeletes++;
164 [ - + ][ # # ]: 2 : } else if (item->action == WAL_ACT_LOGICAL_REMOVE &&
165 : 0 : !doc->deleted) {
166 : 0 : shandle->stat.wal_ndeletes--;
167 : : }
168 : :
169 [ - + ]: 2 : item->action = doc->deleted ? WAL_ACT_LOGICAL_REMOVE : WAL_ACT_INSERT;
170 : 2 : item->offset = offset;
171 : : }
172 : :
173 : 227 : return FDB_RESULT_SUCCESS;
174 : : }
175 : :
176 : 359724 : fdb_status snap_find(struct snap_handle *shandle, fdb_doc *doc,
177 : : uint64_t *offset)
178 : : {
179 : : struct snap_wal_entry query;
180 : : struct avl_node *node;
181 : 359724 : memset(&query, 0, sizeof(snap_wal_entry));
182 [ + + ][ + # ]: 359724 : if (doc->seqnum == SEQNUM_NOT_USED || (doc->key && doc->keylen > 0)) {
[ + + ]
183 [ - + ]: 359723 : if (!shandle->key_tree) {
184 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
185 : : }
186 : : // search by key
187 : 359723 : query.key = doc->key;
188 : 359723 : query.keylen = doc->keylen;
189 : 359723 : node = avl_search(shandle->key_tree, &query.avl, _snp_wal_cmp);
190 [ + + ]: 359774 : if (!node) {
191 : 359573 : return FDB_RESULT_KEY_NOT_FOUND;
192 : : } else {
193 : : struct snap_wal_entry *item;
194 : 201 : item = _get_entry(node, struct snap_wal_entry, avl);
195 : 201 : *offset = item->offset;
196 [ + - ]: 201 : if (item->action == WAL_ACT_INSERT) {
197 : 201 : doc->deleted = false;
198 : : } else {
199 : 0 : doc->deleted = true;
200 : : }
201 : 201 : return FDB_RESULT_SUCCESS;
202 : : }
203 : : } else {
204 [ - + ]: 1 : if (!shandle->seq_tree) {
205 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
206 : : }
207 : : // search by sequence number
208 : 1 : query.seqnum = doc->seqnum;
209 : 1 : node = avl_search(shandle->seq_tree, &query.avl_seq, _snp_seqnum_cmp);
210 [ - + ]: 1 : if (!node) {
211 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
212 : : } else {
213 : : struct snap_wal_entry *item;
214 : 1 : item = _get_entry(node, struct snap_wal_entry, avl_seq);
215 : 1 : *offset = item->offset;
216 [ + - ]: 1 : if (item->action == WAL_ACT_INSERT) {
217 : 1 : doc->deleted = false;
218 : : } else {
219 : 0 : doc->deleted = true;
220 : : }
221 : 359775 : return FDB_RESULT_SUCCESS;
222 : : }
223 : : }
224 : : return FDB_RESULT_KEY_NOT_FOUND;
225 : : }
226 : :
227 : 2 : fdb_status snap_clone(struct snap_handle *shandle_in, fdb_seqnum_t in_seqnum,
228 : : struct snap_handle **shandle, fdb_seqnum_t snap_seqnum)
229 : : {
230 [ + + ][ + - ]: 2 : if (snap_seqnum == FDB_SNAPSHOT_INMEM ||
231 : : in_seqnum == snap_seqnum) {
232 : 2 : spin_lock(&shandle_in->lock);
233 : 2 : shandle_in->ref_cnt++;
234 : 2 : spin_unlock(&shandle_in->lock);
235 : 2 : *shandle = shandle_in;
236 : 2 : return FDB_RESULT_SUCCESS;
237 : : }
238 : :
239 : 2 : return FDB_RESULT_INVALID_ARGS;
240 : : }
241 : :
242 : 35 : fdb_status snap_close(struct snap_handle *shandle)
243 : : {
244 : : struct avl_node *a;
245 : : struct snap_wal_entry *snap_item;
246 : :
247 : 35 : spin_lock(&shandle->lock);
248 [ - + ]: 35 : assert(shandle->ref_cnt);
249 : :
250 [ + + ]: 35 : if (--shandle->ref_cnt == 0) {
251 [ + - ]: 33 : if (shandle->key_tree) {
252 : 33 : a = avl_first(shandle->key_tree);
253 [ + + ]: 258 : while (a) {
254 : 225 : snap_item = _get_entry(a, struct snap_wal_entry, avl);
255 : 225 : a = avl_next(a);
256 : 225 : avl_remove(shandle->key_tree, &snap_item->avl);
257 : 225 : free(snap_item->key);
258 : 225 : free(snap_item);
259 : : }
260 : 33 : free(shandle->key_tree);
261 : 33 : free(shandle->seq_tree);
262 : : }
263 : 33 : spin_unlock(&shandle->lock);
264 : 33 : free(shandle);
265 : : } else {
266 : 2 : spin_unlock(&shandle->lock);
267 : : }
268 : :
269 : 35 : return FDB_RESULT_SUCCESS;
270 : : }
271 : :
272 : 6 : fdb_status snap_get_stat(struct snap_handle *shandle, struct kvs_stat *stat)
273 : : {
274 : 6 : *stat = shandle->stat;
275 : 6 : return FDB_RESULT_SUCCESS;
276 : : }
277 : :
|
