1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
#ifndef _BCACHEFS_HASHTABLE_H
#define _BCACHEFS_HASHTABLE_H
#include <linux/rhashtable.h>
struct htable_params {
u16 key_len;
u16 key_offset;
u16 head_offset;
};
struct htable {
struct mutex lock;
unsigned hash_seed;
unsigned nelems;
unsigned max_chain;
unsigned long table;
};
void bch2_htable_expand(struct htable *, const struct htable_params);
static inline unsigned htable_key_get_hash(const void *key,
unsigned hash_rnd,
const struct htable_params p)
{
return p.key_len % sizeof(u32)
? jhash(key, p.key_len, hash_rnd)
: jhash2(key, p.key_len / sizeof(u32), hash_rnd);
}
static inline unsigned htable_obj_get_hash(const void *obj,
unsigned hash_rnd,
const struct htable_params p)
{
return htable_key_get_hash(obj + p.key_offset, hash_rnd, p);
}
struct htable_ptr {
struct hlist_head *table;
unsigned size;
};
static inline struct htable_ptr htable_read_ptr(struct htable *ht)
{
unsigned long table = READ_ONCE(ht->table);
return (struct htable_ptr) {
.table = (void *) (table & PAGE_MASK),
.size = (PAGE_SIZE / sizeof(void *)) << (table & ~PAGE_MASK),
};
}
static inline struct hlist_head *htable_bucket(struct htable_ptr t,
unsigned hash)
{
return t.table + (hash & (t.size - 1));
}
static inline void *htable_obj(struct hlist_node *n,
const struct htable_params p)
{
return (char *)n - p.head_offset;
}
static inline int htable_cmp(const void *key, const void *obj,
const struct htable_params p)
{
return memcmp(obj + p.key_offset, key, p.key_len);
}
static inline void *__htable_lookup(struct hlist_head *hash_head,
const void *key,
const struct htable_params p)
{
struct hlist_node *n;
__hlist_for_each_rcu(n, hash_head)
if (!htable_cmp(key, htable_obj(n, p), p))
return htable_obj(n, p);
return NULL;
}
static inline void *htable_lookup(struct htable *ht, const void *key,
const struct htable_params p)
{
struct htable_ptr t;
unsigned hash;
void *ret = NULL;
rcu_read_lock();
t = htable_read_ptr(ht);
hash = htable_key_get_hash(key, ht->hash_seed, p);
ret = __htable_lookup(htable_bucket(t, hash), key, p);
rcu_read_unlock();
return ret;
}
static inline void htable_remove(struct htable *ht, void *obj,
const struct htable_params p)
{
struct hlist_node *n;
struct htable_ptr t;
unsigned hash;
int ret = -ENOENT;
mutex_lock(&ht->lock);
t = htable_read_ptr(ht);
hash = htable_obj_get_hash(obj, ht->hash_seed, p);
__hlist_for_each_rcu(n, htable_bucket(t, hash))
if (obj == htable_obj(n, p)) {
hlist_del_rcu(obj + p.head_offset);
ht->nelems--;
ret = 0;
break;
}
mutex_unlock(&ht->lock);
}
static inline int htable_insert(struct htable *ht, void *obj,
const struct htable_params p)
{
struct htable_ptr t;
struct hlist_head *head;
struct hlist_node *n;
unsigned hash, chainlen = 1;
hash = htable_obj_get_hash(obj, ht->hash_seed, p);
mutex_lock(&ht->lock);
t = htable_read_ptr(ht);
head = htable_bucket(t, hash);
__hlist_for_each_rcu(n, head) {
if (!htable_cmp(obj + p.key_offset, htable_obj(n, p), p)) {
mutex_unlock(&ht->lock);
return -EEXIST;
}
chainlen++;
}
hlist_add_head_rcu(obj + p.head_offset, head);
ht->nelems++;
if (chainlen > ht->max_chain) {
ht->max_chain = chainlen;
printk(KERN_INFO "%pf ht with %u/%u has chain %u",
(void *) _THIS_IP_, ht->nelems, t.size, ht->max_chain);
}
if (ht->nelems > t.size >> 2)
bch2_htable_expand(ht, p);
mutex_unlock(&ht->lock);
return 0;
}
void bch2_htable_exit(struct htable *);
int bch2_htable_init(struct htable *);
#endif /* _BCACHEFS_HASHTABLE_H */
|
