Coverage Report

Created: 2019-07-03 22:50

/home/liu/buildslave/linux-x64-runtests/build/lib/ccv_cache.c
Line
Count
Source (jump to first uncovered line)
1
#include "ccv.h"
2
#include "ccv_internal.h"
3
4
6.33M
#define CCV_GET_CACHE_TYPE(x) ((x) >> 60)
5
98.0M
#define CCV_GET_TERMINAL_AGE(x) (((x) >> 32) & 0x0FFFFFFF)
6
5.66M
#define CCV_GET_TERMINAL_SIZE(x) ((x) & 0xFFFFFFFF)
7
6.33M
#define CCV_SET_TERMINAL_TYPE(x, y, z) (((uint64_t)(x) << 60) | ((uint64_t)(y) << 32) | (z))
8
9
void ccv_cache_init(ccv_cache_t* cache, size_t up, int cache_types, ccv_cache_index_free_f ffree, ...)
10
4
{
11
4
  cache->rnum = 0;
12
4
  cache->age = 0;
13
4
  cache->up = up;
14
4
  cache->size = 0;
15
4
  assert(cache_types > 0 && cache_types <= 16);
16
4
  va_list arguments;
17
4
  va_start(arguments, ffree);
18
4
  int i;
19
4
  cache->ffree[0] = ffree;
20
7
  for (i = 1; i < cache_types; 
i++3
)
21
3
    cache->ffree[i] = va_arg(arguments, ccv_cache_index_free_f);
22
4
  va_end(arguments);
23
4
  memset(&cache->origin, 0, sizeof(ccv_cache_index_t));
24
4
}
25
26
static int bits_in_16bits[0x1u << 16];
27
static int bits_in_16bits_init = 0;
28
29
65.5k
static int sparse_bitcount(unsigned int n) {
30
65.5k
  int count = 0;
31
589k
  while (n) {
32
524k
    count++;
33
524k
    n &= (n - 1);
34
524k
  }
35
65.5k
  return count;
36
65.5k
}
37
38
1
static void precomputed_16bits() {
39
1
  int i;
40
65.5k
  for (i = 0; i < (0x1u << 16); 
i++65.5k
)
41
65.5k
    bits_in_16bits[i] = sparse_bitcount(i);
42
1
  bits_in_16bits_init = 1;
43
1
}
44
45
79.3M
static uint32_t compute_bits(uint64_t m) {
46
79.3M
  return (bits_in_16bits[m & 0xffff] + bits_in_16bits[(m >> 16) & 0xffff] +
47
79.3M
      bits_in_16bits[(m >> 32) & 0xffff] + bits_in_16bits[(m >> 48) & 0xffff]);
48
79.3M
}
49
50
/* update age along a path in the radix tree */
51
static void _ccv_cache_aging(ccv_cache_index_t* branch, uint64_t sign)
52
5.66M
{
53
5.66M
  if (!bits_in_16bits_init)
54
0
    precomputed_16bits();
55
5.66M
  int i;
56
5.66M
  uint64_t j = 63;
57
5.66M
  ccv_cache_index_t* breadcrumb[10];
58
22.1M
  for (i = 0; i < 10; 
i++16.4M
)
59
22.1M
  {
60
22.1M
    breadcrumb[i] = branch;
61
22.1M
    int leaf = branch->terminal.off & 0x1;
62
22.1M
    int full = branch->terminal.off & 0x2;
63
22.1M
    if (leaf)
64
1.71M
    {
65
1.71M
      break;
66
20.4M
    } else {
67
20.4M
      ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
68
20.4M
      int dice = (sign & j) >> (i * 6);
69
20.4M
      if (full)
70
12.0M
      {
71
12.0M
        branch = set + dice;
72
12.0M
      } else {
73
8.36M
        uint64_t k = 1;
74
8.36M
        k = k << dice;
75
8.36M
        if (k & branch->branch.bitmap) {
76
4.41M
          uint64_t m = (k - 1) & branch->branch.bitmap;
77
4.41M
          branch = set + compute_bits(m);
78
4.41M
        } else {
79
3.94M
          break;
80
3.94M
        }
81
16.4M
      }
82
16.4M
      j <<= 6;
83
16.4M
    }
84
22.1M
  }
85
5.66M
  assert(i < 10);
86
27.8M
  
for (; 5.66M
i >= 0;
i--22.1M
)
87
22.1M
  {
88
22.1M
    branch = breadcrumb[i];
89
22.1M
    int leaf = branch->terminal.off & 0x1;
90
22.1M
    if (!leaf)
91
20.4M
    {
92
20.4M
      ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
93
20.4M
      uint32_t total = compute_bits(branch->branch.bitmap);
94
20.4M
      uint32_t min_age = (set[0].terminal.off & 0x1) ? 
CCV_GET_TERMINAL_AGE5.21M
(set[0].terminal.type) :
set[0].branch.age15.2M
;
95
1.02G
      for (j = 1; j < total; 
j++1.00G
)
96
1.00G
      {
97
1.00G
        uint32_t age = (set[j].terminal.off & 0x1) ? 
CCV_GET_TERMINAL_AGE83.4M
(set[j].terminal.type) :
set[j].branch.age923M
;
98
1.00G
        if (age < min_age)
99
68.9M
          min_age = age;
100
1.00G
      }
101
20.4M
      branch->branch.age = min_age;
102
20.4M
    }
103
22.1M
  }
104
5.66M
}
105
106
static ccv_cache_index_t* _ccv_cache_seek(ccv_cache_index_t* branch, uint64_t sign, int* depth)
107
7.33M
{
108
7.33M
  if (!bits_in_16bits_init)
109
1
    precomputed_16bits();
110
7.33M
  int i;
111
7.33M
  uint64_t j = 63;
112
29.2M
  for (i = 0; i < 10; 
i++21.8M
)
113
29.2M
  {
114
29.2M
    int leaf = branch->terminal.off & 0x1;
115
29.2M
    int full = branch->terminal.off & 0x2;
116
29.2M
    if (leaf)
117
2.66M
    {
118
2.66M
      if (depth)
119
1.92M
        *depth = i;
120
2.66M
      return branch;
121
26.5M
    } else {
122
26.5M
      ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
123
26.5M
      int dice = (sign & j) >> (i * 6);
124
26.5M
      if (full)
125
15.3M
      {
126
15.3M
        branch = set + dice;
127
15.3M
      } else {
128
11.1M
        uint64_t k = 1;
129
11.1M
        k = k << dice;
130
11.1M
        if (k & branch->branch.bitmap) {
131
6.48M
          uint64_t m = (k - 1) & branch->branch.bitmap;
132
6.48M
          branch = set + compute_bits(m);
133
6.48M
        } else {
134
4.66M
          if (depth)
135
4.41M
            *depth = i;
136
4.66M
          return branch;
137
4.66M
        }
138
21.8M
      }
139
21.8M
      j <<= 6;
140
21.8M
    }
141
29.2M
  }
142
7.33M
  
return 00
;
143
7.33M
}
144
145
void* ccv_cache_get(ccv_cache_t* cache, uint64_t sign, uint8_t* type)
146
1.00M
{
147
1.00M
  if (cache->rnum == 0)
148
0
    return 0;
149
1.00M
  ccv_cache_index_t* branch = _ccv_cache_seek(&cache->origin, sign, 0);
150
1.00M
  if (!branch)
151
0
    return 0;
152
1.00M
  int leaf = branch->terminal.off & 0x1;
153
1.00M
  if (!leaf)
154
255k
    return 0;
155
744k
  if (branch->terminal.sign != sign)
156
77.7k
    return 0;
157
666k
  if (type)
158
0
    *type = CCV_GET_CACHE_TYPE(branch->terminal.type);
159
666k
  return (void*)(branch->terminal.off - (branch->terminal.off & 0x3));
160
666k
}
161
162
// only call this function when the cache space is delpeted
163
static void _ccv_cache_lru(ccv_cache_t* cache)
164
849k
{
165
849k
  ccv_cache_index_t* branch = &cache->origin;
166
849k
  int leaf = branch->terminal.off & 0x1;
167
849k
  if (leaf)
168
0
  {
169
0
    void* result = (void*)(branch->terminal.off - (branch->terminal.off & 0x3));
170
0
    uint8_t type = CCV_GET_CACHE_TYPE(branch->terminal.type);
171
0
    if (result != 0)
172
0
    {
173
0
      assert(type >= 0 && type < 16);
174
0
      cache->ffree[type](result);
175
0
    }
176
0
    cache->rnum = 0;
177
0
    cache->size = 0;
178
0
    return;
179
849k
  }
180
849k
  uint32_t min_age = branch->branch.age;
181
849k
  int i, j;
182
4.18M
  for (i = 0; i < 10; 
i++3.33M
)
183
4.18M
  {
184
4.18M
    ccv_cache_index_t* old_branch = branch;
185
4.18M
    int leaf = branch->terminal.off & 0x1;
186
4.18M
    if (leaf)
187
849k
    {
188
849k
      ccv_cache_delete(cache, branch->terminal.sign);
189
849k
      break;
190
3.33M
    } else {
191
3.33M
      ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
192
3.33M
      uint32_t total = compute_bits(branch->branch.bitmap);
193
81.7M
      for (j = 0; j < total; 
j++78.3M
)
194
81.7M
      {
195
81.7M
        uint32_t age = (set[j].terminal.off & 0x1) ? 
CCV_GET_TERMINAL_AGE7.83M
(set[j].terminal.type) :
set[j].branch.age73.8M
;
196
81.7M
        assert(age >= min_age);
197
81.7M
        if (age == min_age)
198
3.33M
        {
199
3.33M
          branch = set + j;
200
3.33M
          break;
201
3.33M
        }
202
81.7M
      }
203
3.33M
      assert(old_branch != branch);
204
3.33M
    }
205
4.18M
  }
206
849k
  assert(i < 10);
207
849k
}
208
209
static void _ccv_cache_depleted(ccv_cache_t* cache, size_t size)
210
849k
{
211
1.69M
  while (cache->size > size)
212
849k
    _ccv_cache_lru(cache);
213
849k
}
214
215
int ccv_cache_put(ccv_cache_t* cache, uint64_t sign, void* x, uint32_t size, uint8_t type)
216
6.33M
{
217
6.33M
  assert(((uint64_t)x & 0x3) == 0);
218
6.33M
  if (size > cache->up)
219
0
    return -1;
220
6.33M
  if (size + cache->size > cache->up)
221
849k
    _ccv_cache_depleted(cache, cache->up - size);
222
6.33M
  if (cache->rnum == 0)
223
5
  {
224
5
    cache->age = 1;
225
5
    cache->origin.terminal.off = (uint64_t)x | 0x1;
226
5
    cache->origin.terminal.sign = sign;
227
5
    cache->origin.terminal.type = CCV_SET_TERMINAL_TYPE(type, cache->age, size);
228
5
    cache->size = size;
229
5
    cache->rnum = 1;
230
5
    return 0;
231
5
  }
232
6.33M
  ++cache->age;
233
6.33M
  int i, depth = -1;
234
6.33M
  ccv_cache_index_t* branch = _ccv_cache_seek(&cache->origin, sign, &depth);
235
6.33M
  if (!branch)
236
0
    return -1;
237
6.33M
  int leaf = branch->terminal.off & 0x1;
238
6.33M
  uint64_t on = 1;
239
6.33M
  assert(depth >= 0);
240
6.33M
  if (leaf)
241
1.92M
  {
242
1.92M
    if (sign == branch->terminal.sign)
243
443k
    {
244
443k
      cache->ffree[CCV_GET_CACHE_TYPE(branch->terminal.type)]((void*)(branch->terminal.off - (branch->terminal.off & 0x3)));
245
443k
      branch->terminal.off = (uint64_t)x | 0x1;
246
443k
      uint32_t old_size = CCV_GET_TERMINAL_SIZE(branch->terminal.type);
247
443k
      cache->size = cache->size + size - old_size;
248
443k
      branch->terminal.type = CCV_SET_TERMINAL_TYPE(type, cache->age, size);
249
443k
      _ccv_cache_aging(&cache->origin, sign);
250
443k
      return 1;
251
1.47M
    } else {
252
1.47M
      ccv_cache_index_t t = *branch;
253
1.47M
      uint32_t age = CCV_GET_TERMINAL_AGE(branch->terminal.type);
254
1.47M
      uint64_t j = 63;
255
1.47M
      j = j << (depth * 6);
256
1.47M
      int dice, udice;
257
1.47M
      assert(depth < 10);
258
1.50M
      
for (i = depth; 1.47M
i < 10;
i++23.4k
)
259
1.50M
      {
260
1.50M
        dice = (t.terminal.sign & j) >> (i * 6);
261
1.50M
        udice = (sign & j) >> (i * 6);
262
1.50M
        if (dice == udice)
263
23.4k
        {
264
23.4k
          branch->branch.bitmap = on << dice;
265
23.4k
          ccv_cache_index_t* set = (ccv_cache_index_t*)ccmalloc(sizeof(ccv_cache_index_t));
266
23.4k
          assert(((uint64_t)set & 0x3) == 0);
267
23.4k
          branch->branch.set = (uint64_t)set;
268
23.4k
          branch->branch.age = age;
269
23.4k
          branch = set;
270
1.47M
        } else {
271
1.47M
          break;
272
1.47M
        }
273
23.4k
        j <<= 6;
274
23.4k
      }
275
1.47M
      branch->branch.bitmap = (on << dice) | (on << udice);
276
1.47M
      ccv_cache_index_t* set = (ccv_cache_index_t*)ccmalloc(sizeof(ccv_cache_index_t) * 2);
277
1.47M
      assert(((uint64_t)set & 0x3) == 0);
278
1.47M
      branch->branch.set = (uint64_t)set;
279
1.47M
      branch->branch.age = age;
280
1.47M
      int u = dice < udice;
281
1.47M
      set[u].terminal.sign = sign;
282
1.47M
      set[u].terminal.off = (uint64_t)x | 0x1;
283
1.47M
      set[u].terminal.type = CCV_SET_TERMINAL_TYPE(type, cache->age, size);
284
1.47M
      set[1 - u] = t;
285
1.47M
    }
286
4.41M
  } else {
287
4.41M
    uint64_t k = 1, j = 63;
288
4.41M
    k = k << ((sign & (j << (depth * 6))) >> (depth * 6));
289
4.41M
    uint64_t m = (k - 1) & branch->branch.bitmap;
290
4.41M
    uint32_t start = compute_bits(m);
291
4.41M
    uint32_t total = compute_bits(branch->branch.bitmap);
292
4.41M
    ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
293
4.41M
    set = (ccv_cache_index_t*)ccrealloc(set, sizeof(ccv_cache_index_t) * (total + 1));
294
4.41M
    assert(((uint64_t)set & 0x3) == 0);
295
31.8M
    
for (i = total; 4.41M
i > start;
i--27.4M
)
296
27.4M
      set[i] = set[i - 1];
297
4.41M
    set[start].terminal.off = (uint64_t)x | 0x1;
298
4.41M
    set[start].terminal.sign = sign;
299
4.41M
    set[start].terminal.type = CCV_SET_TERMINAL_TYPE(type, cache->age, size);
300
4.41M
    branch->branch.set = (uint64_t)set;
301
4.41M
    branch->branch.bitmap |= k;
302
4.41M
    if (total == 63)
303
6.33k
      branch->branch.set |= 0x2;
304
4.41M
  }
305
6.33M
  cache->rnum++;
306
5.88M
  cache->size += size;
307
5.88M
  return 0;
308
6.33M
}
309
310
static void _ccv_cache_cleanup(ccv_cache_index_t* branch)
311
1.29M
{
312
1.29M
  int leaf = branch->terminal.off & 0x1;
313
1.29M
  if (!leaf)
314
1.29M
  {
315
1.29M
    int i;
316
1.29M
    uint64_t total = compute_bits(branch->branch.bitmap);
317
1.29M
    ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
318
3.86M
    for (i = 0; i < total; 
i++2.56M
)
319
2.56M
    {
320
2.56M
      if (!(set[i].terminal.off & 0x1))
321
20.3k
        _ccv_cache_cleanup(set + i);
322
2.56M
    }
323
1.29M
    ccfree(set);
324
1.29M
  }
325
1.29M
}
326
327
static void _ccv_cache_cleanup_and_free(ccv_cache_index_t* branch, ccv_cache_index_free_f ffree[])
328
873k
{
329
873k
  int leaf = branch->terminal.off & 0x1;
330
873k
  if (!leaf)
331
206k
  {
332
206k
    int i;
333
206k
    uint64_t total = compute_bits(branch->branch.bitmap);
334
206k
    ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
335
1.08M
    for (i = 0; i < total; 
i++873k
)
336
873k
      _ccv_cache_cleanup_and_free(set + i, ffree);
337
206k
    ccfree(set);
338
666k
  } else {
339
666k
    assert(CCV_GET_CACHE_TYPE(branch->terminal.type) >= 0 && CCV_GET_CACHE_TYPE(branch->terminal.type) < 16);
340
666k
    ffree[CCV_GET_CACHE_TYPE(branch->terminal.type)]((void*)(branch->terminal.off - (branch->terminal.off & 0x3)));
341
666k
  }
342
873k
}
343
344
void* ccv_cache_out(ccv_cache_t* cache, uint64_t sign, uint8_t* type)
345
5.94M
{
346
5.94M
  if (!bits_in_16bits_init)
347
0
    precomputed_16bits();
348
5.94M
  if (cache->rnum == 0)
349
609k
    return 0;
350
5.33M
  int i, found = 0, depth = -1;
351
5.33M
  ccv_cache_index_t* parent = 0;
352
5.33M
  ccv_cache_index_t* uncle = &cache->origin;
353
5.33M
  ccv_cache_index_t* branch = &cache->origin;
354
5.33M
  uint64_t j = 63;
355
25.6M
  for (i = 0; i < 10; 
i++20.2M
)
356
25.6M
  {
357
25.6M
    int leaf = branch->terminal.off & 0x1;
358
25.6M
    int full = branch->terminal.off & 0x2;
359
25.6M
    if (leaf)
360
5.24M
    {
361
5.24M
      found = 1;
362
5.24M
      break;
363
5.24M
    }
364
20.3M
    if (parent != 0 && 
compute_bits(parent->branch.bitmap) > 115.0M
)
365
15.0M
      uncle = branch;
366
20.3M
    parent = branch;
367
20.3M
    depth = i;
368
20.3M
    ccv_cache_index_t* set = (ccv_cache_index_t*)(branch->branch.set - (branch->branch.set & 0x3));
369
20.3M
    int dice = (sign & j) >> (i * 6);
370
20.3M
    if (full)
371
11.4M
    {
372
11.4M
      branch = set + dice;
373
11.4M
    } else {
374
8.97M
      uint64_t k = 1;
375
8.97M
      k = k << dice;
376
8.97M
      if (k & branch->branch.bitmap)
377
8.88M
      {
378
8.88M
        uint64_t m = (k - 1) & branch->branch.bitmap;
379
8.88M
        branch = set + compute_bits(m);
380
8.88M
      } else {
381
85.2k
        return 0;
382
85.2k
      }
383
20.2M
    }
384
20.2M
    j <<= 6;
385
20.2M
  }
386
5.33M
  
if (5.24M
!found5.24M
)
387
0
    return 0;
388
5.24M
  int leaf = branch->terminal.off & 0x1;
389
5.24M
  if (!leaf)
390
0
    return 0;
391
5.24M
  if (branch->terminal.sign != sign)
392
25.9k
    return 0;
393
5.22M
  void* result = (void*)(branch->terminal.off - (branch->terminal.off & 0x3));
394
5.22M
  if (type)
395
5.22M
    *type = CCV_GET_CACHE_TYPE(branch->terminal.type);
396
5.22M
  uint32_t size = CCV_GET_TERMINAL_SIZE(branch->terminal.type);
397
5.22M
  if (branch != &cache->origin)
398
5.22M
  {
399
5.22M
    uint64_t k = 1, j = 63;
400
5.22M
    int dice = (sign & (j << (depth * 6))) >> (depth * 6);
401
5.22M
    k = k << dice;
402
5.22M
    uint64_t m = (k - 1) & parent->branch.bitmap;
403
5.22M
    uint32_t start = compute_bits(m);
404
5.22M
    uint32_t total = compute_bits(parent->branch.bitmap);
405
5.22M
    assert(total > 1);
406
5.22M
    ccv_cache_index_t* set = (ccv_cache_index_t*)(parent->branch.set - (parent->branch.set & 0x3));
407
5.22M
    if (total > 2 || 
(1.28M
total == 21.28M
&&
!(set[1 - start].terminal.off & 0x1)1.28M
))
408
3.94M
    {
409
3.94M
      parent->branch.bitmap &= ~k;
410
27.5M
      for (i = start + 1; i < total; 
i++23.5M
)
411
23.5M
        set[i - 1] = set[i];
412
3.94M
      set = (ccv_cache_index_t*)ccrealloc(set, sizeof(ccv_cache_index_t) * (total - 1));
413
3.94M
      parent->branch.set = (uint64_t)set;
414
3.94M
    } else {
415
1.27M
      ccv_cache_index_t t = set[1 - start];
416
1.27M
      _ccv_cache_cleanup(uncle);
417
1.27M
      *uncle = t;
418
1.27M
    }
419
5.22M
    _ccv_cache_aging(&cache->origin, sign);
420
5.22M
  } else {
421
4
    // if I only have one item, reset age to 1
422
4
    cache->age = 1;
423
4
  }
424
5.22M
  cache->rnum--;
425
5.22M
  cache->size -= size;
426
5.22M
  return result;
427
5.22M
}
428
429
int ccv_cache_delete(ccv_cache_t* cache, uint64_t sign)
430
2.18M
{
431
2.18M
  uint8_t type = 0;
432
2.18M
  void* result = ccv_cache_out(cache, sign, &type);
433
2.18M
  if (result != 0)
434
2.07M
  {
435
2.07M
    assert(type >= 0 && type < 16);
436
2.07M
    cache->ffree[type](result);
437
2.07M
    return 0;
438
111k
  }
439
111k
  return -1;
440
111k
}
441
442
void ccv_cache_cleanup(ccv_cache_t* cache)
443
4
{
444
4
  if (cache->rnum > 0)
445
1
  {
446
1
    _ccv_cache_cleanup_and_free(&cache->origin, cache->ffree);
447
1
    cache->size = 0;
448
1
    cache->age = 0;
449
1
    cache->rnum = 0;
450
1
    memset(&cache->origin, 0, sizeof(ccv_cache_index_t));
451
1
  }
452
4
}
453
454
void ccv_cache_close(ccv_cache_t* cache)
455
4
{
456
4
  // for radix-tree based cache, close/cleanup are the same (it is not the same for cuckoo based one,
457
4
  // because for cuckoo based one, it will free up space in close whereas only cleanup space in cleanup
458
4
  ccv_cache_cleanup(cache);
459
4
}