glusterfs

1
/*
2
  Copyright (c) 2008-2012 Red Hat, Inc. <http://www.redhat.com>
3
  This file is part of GlusterFS.
4

5
  This file is licensed to you under your choice of the GNU Lesser
6
  General Public License, version 3 or any later version (LGPLv3 or
7
  later), or the GNU General Public License, version 2 (GPLv2), in all
8
  cases as published by the Free Software Foundation.
9
*/
10

11
#include "glusterfs/rbthash.h"
12
#include "rb.h"
13
#include "glusterfs/locking.h"
14
#include "glusterfs/mem-pool.h"
15
#include "glusterfs/libglusterfs-messages.h"
16

17
#include <pthread.h>
18
#include <string.h>
19

20
int
21
rbthash_comparator(void *entry1, void *entry2, void *param)
22
{
23
    int ret = 0;
24
    rbthash_entry_t *e1 = NULL;
25
    rbthash_entry_t *e2 = NULL;
26

27
    if ((!entry1) || (!entry2) || (!param))
28
        return -1;
29

30
    e1 = (rbthash_entry_t *)entry1;
31
    e2 = (rbthash_entry_t *)entry2;
32

33
    if (e1->keylen != e2->keylen) {
34
        if (e1->keylen < e2->keylen)
35
            ret = -1;
36
        else if (e1->keylen > e2->keylen)
37
            ret = 1;
38
    } else
39
        ret = memcmp(e1->key, e2->key, e1->keylen);
40

41
    return ret;
42
}
43

44
int
45
__rbthash_init_buckets(rbthash_table_t *tbl, int buckets)
46
{
47
    int i = 0;
48
    int ret = -1;
49

50
    if (!tbl)
51
        return -1;
52

53
    for (; i < buckets; i++) {
54
        LOCK_INIT(&tbl->buckets[i].bucketlock);
55
        tbl->buckets[i].bucket = rb_create(
56
            (rb_comparison_func *)rbthash_comparator, tbl, NULL);
57
        if (!tbl->buckets[i].bucket) {
58
            gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RB_TABLE_CREATE_FAILED,
59
                    NULL);
60
            ret = -1;
61
            goto err;
62
        }
63
    }
64

65
    ret = 0;
66
err:
67
    return ret;
68
}
69

70
/*
71
 * rbthash_table_init - Initialize a RBT based hash table
72
 * @buckets - Number of buckets in the hash table
73
 * @hfunc   - hashing function
74
 * @dfunc   - destroyer for data in the RBT
75
 * @expected_entries - Number of entries expected in RBT. Mutually exclusive
76
 * with entrypool.
77
 * @entrypool -  Memory pool in lieu of expected_entries.
78
 */
79

80
rbthash_table_t *
81
rbthash_table_init(glusterfs_ctx_t *ctx, int buckets, rbt_hasher_t hfunc,
82
                   rbt_data_destroyer_t dfunc, unsigned long expected_entries,
83
                   struct mem_pool *entrypool)
84
{
85
    rbthash_table_t *newtab = NULL;
86
    int ret = -1;
87

88
    if (!hfunc) {
89
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_HASH_FUNC_ERROR, NULL);
90
        return NULL;
91
    }
92

93
    if (!entrypool && !expected_entries) {
94
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_ENTRIES_NOT_PROVIDED, NULL);
95
        return NULL;
96
    }
97

98
    if (entrypool && expected_entries) {
99
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_ENTRIES_PROVIDED, NULL);
100
        return NULL;
101
    }
102

103
    newtab = GF_CALLOC(1, sizeof(*newtab), gf_common_mt_rbthash_table_t);
104
    if (!newtab)
105
        return NULL;
106

107
    newtab->buckets = GF_CALLOC(buckets, sizeof(struct rbthash_bucket),
108
                                gf_common_mt_rbthash_bucket);
109
    if (!newtab->buckets) {
110
        goto free_newtab;
111
    }
112

113
    if (expected_entries) {
114
        newtab->entrypool = mem_pool_new_ctx(ctx, rbthash_entry_t,
115
                                             expected_entries);
116
        if (!newtab->entrypool) {
117
            goto free_buckets;
118
        }
119
        newtab->pool_alloced = _gf_true;
120
    } else {
121
        newtab->entrypool = entrypool;
122
    }
123

124
    LOCK_INIT(&newtab->tablelock);
125
    INIT_LIST_HEAD(&newtab->list);
126
    newtab->numbuckets = buckets;
127
    ret = __rbthash_init_buckets(newtab, buckets);
128

129
    if (ret == -1) {
130
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_BUCKET_FAILED,
131
                NULL);
132
        if (newtab->pool_alloced)
133
            mem_pool_destroy(newtab->entrypool);
134
    } else {
135
        gf_msg_trace(GF_RBTHASH, 0,
136
                     "Inited hash table: buckets:"
137
                     " %d",
138
                     buckets);
139
    }
140

141
    newtab->hashfunc = hfunc;
142
    newtab->dfunc = dfunc;
143

144
free_buckets:
145
    if (ret == -1)
146
        GF_FREE(newtab->buckets);
147

148
free_newtab:
149
    if (ret == -1) {
150
        GF_FREE(newtab);
151
        newtab = NULL;
152
    }
153

154
    return newtab;
155
}
156

157
rbthash_entry_t *
158
rbthash_init_entry(rbthash_table_t *tbl, void *data, void *key, int keylen)
159
{
160
    int ret = -1;
161
    rbthash_entry_t *entry = NULL;
162

163
    if ((!tbl) || (!data) || (!key))
164
        return NULL;
165

166
    entry = mem_get(tbl->entrypool);
167
    if (!entry) {
168
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_ENTRY_FAILED,
169
                NULL);
170
        goto ret;
171
    }
172

173
    entry->data = data;
174
    entry->key = GF_MALLOC(keylen, gf_common_mt_char);
175
    if (!entry->key) {
176
        goto free_entry;
177
    }
178

179
    INIT_LIST_HEAD(&entry->list);
180
    memcpy(entry->key, key, keylen);
181
    entry->keylen = keylen;
182
    entry->keyhash = tbl->hashfunc(entry->key, entry->keylen);
183
    gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", entry->keyhash);
184

185
    ret = 0;
186
free_entry:
187
    if (ret == -1) {
188
        mem_put(entry);
189
        entry = NULL;
190
    }
191

192
ret:
193
    return entry;
194
}
195

196
void
197
rbthash_deinit_entry(rbthash_table_t *tbl, rbthash_entry_t *entry)
198
{
199
    if (!entry)
200
        return;
201

202
    GF_FREE(entry->key);
203

204
    if (tbl) {
205
        if ((entry->data) && (tbl->dfunc))
206
            tbl->dfunc(entry->data);
207

208
        LOCK(&tbl->tablelock);
209
        {
210
            list_del_init(&entry->list);
211
        }
212
        UNLOCK(&tbl->tablelock);
213

214
        mem_put(entry);
215
    }
216

217
    return;
218
}
219

220
static struct rbthash_bucket *
221
rbthash_entry_bucket(rbthash_table_t *tbl, rbthash_entry_t *entry)
222
{
223
    int nbucket = 0;
224

225
    nbucket = (entry->keyhash % tbl->numbuckets);
226
    gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %d", nbucket);
227
    return &tbl->buckets[nbucket];
228
}
229

230
int
231
rbthash_insert_entry(rbthash_table_t *tbl, rbthash_entry_t *entry)
232
{
233
    struct rbthash_bucket *bucket = NULL;
234
    int ret = -1;
235

236
    if ((!tbl) || (!entry))
237
        return -1;
238

239
    bucket = rbthash_entry_bucket(tbl, entry);
240
    if (!bucket) {
241
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED,
242
                NULL);
243
        goto err;
244
    }
245

246
    ret = 0;
247
    LOCK(&bucket->bucketlock);
248
    {
249
        if (!rb_probe(bucket->bucket, (void *)entry)) {
250
            UNLOCK(&bucket->bucketlock);
251
            gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED,
252
                    NULL);
253
            ret = -1;
254
            goto err;
255
        }
256
    }
257
    UNLOCK(&bucket->bucketlock);
258

259
err:
260
    return ret;
261
}
262

263
int
264
rbthash_insert(rbthash_table_t *tbl, void *data, void *key, int keylen)
265
{
266
    rbthash_entry_t *entry = NULL;
267
    int ret = -1;
268

269
    if ((!tbl) || (!data) || (!key))
270
        return -1;
271

272
    entry = rbthash_init_entry(tbl, data, key, keylen);
273
    if (!entry) {
274
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_ENTRY_FAILED,
275
                NULL);
276
        goto err;
277
    }
278

279
    ret = rbthash_insert_entry(tbl, entry);
280

281
    if (ret == -1) {
282
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED,
283
                NULL);
284
        rbthash_deinit_entry(tbl, entry);
285
        goto err;
286
    }
287

288
    LOCK(&tbl->tablelock);
289
    {
290
        list_add_tail(&entry->list, &tbl->list);
291
    }
292
    UNLOCK(&tbl->tablelock);
293

294
err:
295
    return ret;
296
}
297

298
static struct rbthash_bucket *
299
rbthash_key_bucket(rbthash_table_t *tbl, void *key, int keylen)
300
{
301
    uint32_t keyhash = 0;
302
    int nbucket = 0;
303

304
    if ((!tbl) || (!key))
305
        return NULL;
306

307
    keyhash = tbl->hashfunc(key, keylen);
308
    gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", keyhash);
309
    nbucket = (keyhash % tbl->numbuckets);
310
    gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %u", nbucket);
311

312
    return &tbl->buckets[nbucket];
313
}
314

315
void *
316
rbthash_get(rbthash_table_t *tbl, void *key, int keylen)
317
{
318
    struct rbthash_bucket *bucket = NULL;
319
    rbthash_entry_t *entry = NULL;
320
    rbthash_entry_t searchentry = {
321
        0,
322
    };
323

324
    if ((!tbl) || (!key))
325
        return NULL;
326

327
    bucket = rbthash_key_bucket(tbl, key, keylen);
328
    if (!bucket) {
329
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED,
330
                NULL);
331
        return NULL;
332
    }
333

334
    searchentry.key = key;
335
    searchentry.keylen = keylen;
336
    LOCK(&bucket->bucketlock);
337
    {
338
        entry = rb_find(bucket->bucket, &searchentry);
339
    }
340
    UNLOCK(&bucket->bucketlock);
341

342
    if (!entry)
343
        return NULL;
344

345
    return entry->data;
346
}
347

348
void *
349
rbthash_remove(rbthash_table_t *tbl, void *key, int keylen)
350
{
351
    struct rbthash_bucket *bucket = NULL;
352
    rbthash_entry_t *entry = NULL;
353
    rbthash_entry_t searchentry = {
354
        0,
355
    };
356
    void *dataref = NULL;
357

358
    if ((!tbl) || (!key))
359
        return NULL;
360

361
    bucket = rbthash_key_bucket(tbl, key, keylen);
362
    if (!bucket) {
363
        gf_smsg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED,
364
                NULL);
365
        return NULL;
366
    }
367

368
    searchentry.key = key;
369
    searchentry.keylen = keylen;
370

371
    LOCK(&bucket->bucketlock);
372
    {
373
        entry = rb_delete(bucket->bucket, &searchentry);
374
    }
375
    UNLOCK(&bucket->bucketlock);
376

377
    if (!entry)
378
        return NULL;
379

380
    GF_FREE(entry->key);
381
    dataref = entry->data;
382

383
    LOCK(&tbl->tablelock);
384
    {
385
        list_del_init(&entry->list);
386
    }
387
    UNLOCK(&tbl->tablelock);
388

389
    mem_put(entry);
390

391
    return dataref;
392
}
393

394
void
395
rbthash_entry_deiniter(void *entry, void *rbparam)
396
{
397
    if (!entry)
398
        return;
399

400
    rbthash_deinit_entry(rbparam, entry);
401
}
402

403
void
404
rbthash_table_destroy_buckets(rbthash_table_t *tbl)
405
{
406
    int x = 0;
407
    if (!tbl)
408
        return;
409

410
    for (; x < tbl->numbuckets; x++) {
411
        LOCK_DESTROY(&tbl->buckets[x].bucketlock);
412
        rb_destroy(tbl->buckets[x].bucket, rbthash_entry_deiniter);
413
    }
414

415
    return;
416
}
417

418
void
419
rbthash_table_destroy(rbthash_table_t *tbl)
420
{
421
    if (!tbl)
422
        return;
423

424
    rbthash_table_destroy_buckets(tbl);
425
    if (tbl->pool_alloced)
426
        mem_pool_destroy(tbl->entrypool);
427

428
    LOCK_DESTROY(&tbl->tablelock);
429
    GF_FREE(tbl->buckets);
430
    GF_FREE(tbl);
431
}
432

433
void
434
rbthash_table_traverse(rbthash_table_t *tbl, rbt_traverse_t traverse,
435
                       void *mydata)
436
{
437
    rbthash_entry_t *entry = NULL;
438

439
    if ((tbl == NULL) || (traverse == NULL)) {
440
        goto out;
441
    }
442

443
    LOCK(&tbl->tablelock);
444
    {
445
        list_for_each_entry(entry, &tbl->list, list)
446
        {
447
            traverse(entry->data, mydata);
448
        }
449
    }
450
    UNLOCK(&tbl->tablelock);
451

452
out:
453
    return;
454
}
455