1 #include "config.h"
2 #include <sys/types.h>
3 #include <stdlib.h>
4 #include <inttypes.h>
5 #include <string.h>
6 #include <platform/platform.h>
7 #include "topkeys.h"
8 
topkey_item_init(const void *key, int nkey, rel_time_t ct)9 static topkey_item_t *topkey_item_init(const void *key, int nkey, rel_time_t ct) {
10     topkey_item_t *it = calloc(sizeof(topkey_item_t) + nkey, 1);
11     cb_assert(it);
12     cb_assert(key);
13     cb_assert(nkey > 0);
14     it->ti_nkey = nkey;
15     it->ti_ctime = ct;
16     it->ti_atime = ct;
17     /* Copy the key into the part trailing the struct */
18     memcpy(it + 1, key, nkey);
19     return it;
20 }
21 
topkey_item_size(const topkey_item_t *it)22 static size_t topkey_item_size(const topkey_item_t *it) {
23     return sizeof(topkey_item_t) + it->ti_nkey;
24 }
25 
topkeys_tail(topkeys_t *tk)26 static topkey_item_t* topkeys_tail(topkeys_t *tk) {
27     return (topkey_item_t*)(tk->list.prev);
28 }
29 
my_hash_eq(const void *k1, size_t nkey1, const void *k2, size_t nkey2)30 static int my_hash_eq(const void *k1, size_t nkey1,
31                       const void *k2, size_t nkey2) {
32     return nkey1 == nkey2 && memcmp(k1, k2, nkey1) == 0;
33 }
34 
topkeys_init(int max_keys)35 topkeys_t *topkeys_init(int max_keys) {
36     static struct hash_ops my_hash_ops;
37     topkeys_t *tk = calloc(sizeof(topkeys_t), 1);
38     if (tk == NULL) {
39         return NULL;
40     }
41 
42     my_hash_ops.hashfunc = genhash_string_hash;
43     my_hash_ops.hasheq = my_hash_eq;
44     my_hash_ops.dupKey = NULL;
45     my_hash_ops.dupValue = NULL;
46     my_hash_ops.freeKey = NULL;
47     my_hash_ops.freeValue = NULL;
48 
49     cb_mutex_initialize(&tk->mutex);
50     tk->max_keys = max_keys;
51     tk->list.next = &tk->list;
52     tk->list.prev = &tk->list;
53 
54     tk->hash = genhash_init(max_keys, my_hash_ops);
55     if (tk->hash == NULL) {
56         return NULL;
57     }
58 
59     return tk;
60 }
61 
topkeys_free(topkeys_t *tk)62 void topkeys_free(topkeys_t *tk) {
63     dlist_t *p;
64     cb_mutex_destroy(&tk->mutex);
65     genhash_free(tk->hash);
66     p = tk->list.next;
67     while (p != &tk->list) {
68         dlist_t *tmp = p->next;
69         free(p);
70         p = tmp;
71     }
72 }
73 
dlist_remove(dlist_t *list)74 static void dlist_remove(dlist_t *list) {
75     cb_assert(list->prev->next == list);
76     cb_assert(list->next->prev == list);
77     list->prev->next = list->next;
78     list->next->prev = list->prev;
79 }
80 
dlist_insert_after(dlist_t *list, dlist_t *new)81 static void dlist_insert_after(dlist_t *list, dlist_t *new) {
82     new->next = list->next;
83     new->prev = list;
84     list->next->prev = new;
85     list->next = new;
86 }
87 
dlist_iter(dlist_t *list, void (*iterfunc)(dlist_t *item, void *arg), void *arg)88 static void dlist_iter(dlist_t *list,
89                               void (*iterfunc)(dlist_t *item, void *arg),
90                               void *arg)
91 {
92     dlist_t *p = list;
93     while ((p = p->next) != list) {
94         iterfunc(p, arg);
95     }
96 }
97 
topkeys_item_delete(topkeys_t *tk, topkey_item_t *it)98 static void topkeys_item_delete(topkeys_t *tk, topkey_item_t *it) {
99     genhash_delete(tk->hash, it + 1, it->ti_nkey);
100     dlist_remove(&it->ti_list);
101     --tk->nkeys;
102     free(it);
103 }
104 
topkeys_item_get_or_create(topkeys_t *tk, const void *key, size_t nkey, const rel_time_t ct)105 topkey_item_t *topkeys_item_get_or_create(topkeys_t *tk, const void *key, size_t nkey, const rel_time_t ct) {
106     topkey_item_t *it = genhash_find(tk->hash, key, nkey);
107     if (it == NULL) {
108         it = topkey_item_init(key, (int)nkey, ct);
109         if (it != NULL) {
110             if (++tk->nkeys > tk->max_keys) {
111                 topkeys_item_delete(tk, topkeys_tail(tk));
112             }
113             genhash_update(tk->hash, it + 1, it->ti_nkey,
114                            it, topkey_item_size(it));
115         } else {
116             return NULL;
117         }
118     } else {
119         dlist_remove(&it->ti_list);
120     }
121     dlist_insert_after(&tk->list, &it->ti_list);
122     return it;
123 }
124 
125 struct tk_context {
126     const void *cookie;
127     ADD_STAT add_stat;
128     rel_time_t current_time;
129 };
130 
131 #define TK_FMT(name) #name "=%d,"
132 #define TK_ARGS(name) it->name,
133 
tk_iterfunc(dlist_t *list, void *arg)134 static void tk_iterfunc(dlist_t *list, void *arg) {
135     struct tk_context *c = arg;
136     topkey_item_t *it = (topkey_item_t*)list;
137     char val_str[TK_MAX_VAL_LEN];
138     /* This line is magical. The missing comma before item->ctime is because the TK_ARGS macro ends with a comma. */
139     int vlen = snprintf(val_str, sizeof(val_str) - 1, TK_OPS(TK_FMT)"ctime=%"PRIu32",atime=%"PRIu32, TK_OPS(TK_ARGS)
140                         c->current_time - it->ti_ctime, c->current_time - it->ti_atime);
141     c->add_stat((char*)(it + 1), it->ti_nkey, val_str, vlen, c->cookie);
142 }
143 
topkeys_stats(topkeys_t **tks, size_t shards, const void *cookie, const rel_time_t current_time, ADD_STAT add_stat)144 ENGINE_ERROR_CODE topkeys_stats(topkeys_t **tks, size_t shards,
145                                 const void *cookie,
146                                 const rel_time_t current_time,
147                                 ADD_STAT add_stat) {
148     struct tk_context context;
149     size_t i;
150     context.cookie = cookie;
151     context.add_stat = add_stat;
152     context.current_time = current_time;
153     for (i = 0; i < shards; i++) {
154         topkeys_t *tk = tks[i];
155         cb_assert(tk);
156         cb_mutex_enter(&tk->mutex);
157         dlist_iter(&tk->list, tk_iterfunc, &context);
158         cb_mutex_exit(&tk->mutex);
159     }
160     return ENGINE_SUCCESS;
161 }
162 
tk_get_shard(topkeys_t **tks, const void *key, size_t nkey)163 topkeys_t *tk_get_shard(topkeys_t **tks, const void *key, size_t nkey) {
164     /* This is special-cased for 8 */
165     int khash;
166     cb_assert(TK_SHARDS == 8);
167     khash = genhash_string_hash(key, nkey);
168     return tks[khash & 0x07];
169 }
170