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
166
167
168
169
170
171
172
173
174
175
176
177
|
/*
Copyright (c) 2008-2012 Red Hat, Inc. <http://www.redhat.com>
This file is part of GlusterFS.
This file is licensed to you under your choice of the GNU Lesser
General Public License, version 3 or any later version (LGPLv3 or
later), or the GNU General Public License, version 2 (GPLv2), in all
cases as published by the Free Software Foundation.
*/
#include "gidcache.h"
#include "mem-pool.h"
/*
* We treat this as a very simple set-associative LRU cache, with entries aged
* out after a configurable interval. Hardly rocket science, but lots of
* details to worry about.
*/
#define BUCKET_START(p,n) ((p) + ((n) * AUX_GID_CACHE_ASSOC))
/*
* Initialize the cache.
*/
int gid_cache_init(gid_cache_t *cache, uint32_t timeout)
{
if (!cache)
return -1;
LOCK_INIT(&cache->gc_lock);
cache->gc_max_age = timeout;
cache->gc_nbuckets = AUX_GID_CACHE_BUCKETS;
memset(cache->gc_cache, 0, sizeof(gid_list_t) * AUX_GID_CACHE_SIZE);
return 0;
}
/*
* Look up an ID in the cache. If found, return the actual cache entry to avoid
* an additional allocation and memory copy. The caller should copy the data and
* release (unlock) the cache as soon as possible.
*/
const gid_list_t *gid_cache_lookup(gid_cache_t *cache, uint64_t id)
{
int bucket;
int i;
time_t now;
const gid_list_t *agl;
LOCK(&cache->gc_lock);
now = time(NULL);
bucket = id % cache->gc_nbuckets;
agl = BUCKET_START(cache->gc_cache, bucket);
for (i = 0; i < AUX_GID_CACHE_ASSOC; i++, agl++) {
if (!agl->gl_list)
continue;
if (agl->gl_id != id)
continue;
/*
* We don't put new entries in the cache when expiration=0, but
* there might be entries still in there if expiration was
* changed very recently. Writing the check this way ensures
* that they're not used.
*/
if (now < agl->gl_deadline) {
return agl;
}
/*
* We're not going to find any more UID matches, and reaping
* is handled further down to maintain LRU order.
*/
break;
}
UNLOCK(&cache->gc_lock);
return NULL;
}
/*
* Release an entry found via lookup.
*/
void gid_cache_release(gid_cache_t *cache, const gid_list_t *agl)
{
UNLOCK(&cache->gc_lock);
}
/*
* Add a new list entry to the cache. If an entry for this ID already exists,
* update it.
*/
int gid_cache_add(gid_cache_t *cache, gid_list_t *gl)
{
gid_list_t *agl;
int bucket;
int i;
time_t now;
if (!gl || !gl->gl_list)
return -1;
if (!cache->gc_max_age)
return 0;
LOCK(&cache->gc_lock);
now = time(NULL);
/*
* Scan for the first free entry or one that matches this id. The id
* check is added to address a bug where the cache might contain an
* expired entry for this id. Since lookup occurs in LRU order and
* does not reclaim entries, it will always return failure on discovery
* of an expired entry. This leads to duplicate entries being added,
* which still do not satisfy lookups until the expired entry (and
* everything before it) is reclaimed.
*
* We address this through reuse of an entry already allocated to this
* id, whether expired or not, since we have obviously already received
* more recent data. The entry is repopulated with the new data and a new
* deadline and is pushed forward to reside as the last populated entry in
* the bucket.
*/
bucket = gl->gl_id % cache->gc_nbuckets;
agl = BUCKET_START(cache->gc_cache, bucket);
for (i = 0; i < AUX_GID_CACHE_ASSOC; ++i, ++agl) {
if (agl->gl_id == gl->gl_id)
break;
if (!agl->gl_list)
break;
}
/*
* The way we allocate free entries naturally places the newest
* ones at the highest indices, so evicting the lowest makes
* sense, but that also means we can't just replace it with the
* one that caused the eviction. That would cause us to thrash
* the first entry while others remain idle. Therefore, we
* need to slide the other entries down and add the new one at
* the end just as if the *last* slot had been free.
*
* Deadline expiration is also handled here, since the oldest
* expired entry will be in the first position. This does mean
* the bucket can stay full of expired entries if we're idle
* but, if the small amount of extra memory or scan time before
* we decide to evict someone ever become issues, we could
* easily add a reaper thread.
*/
if (i >= AUX_GID_CACHE_ASSOC) {
/* cache full, evict the first (LRU) entry */
i = 0;
agl = BUCKET_START(cache->gc_cache, bucket);
GF_FREE(agl->gl_list);
} else if (agl->gl_list) {
/* evict the old entry we plan to reuse */
GF_FREE(agl->gl_list);
}
/*
* If we have evicted an entry, slide the subsequent populated entries
* back and populate the last entry.
*/
for (; i < AUX_GID_CACHE_ASSOC - 1; i++) {
if (!agl[1].gl_list)
break;
agl[0] = agl[1];
agl++;
}
agl->gl_id = gl->gl_id;
agl->gl_count = gl->gl_count;
agl->gl_list = gl->gl_list;
agl->gl_deadline = now + cache->gc_max_age;
UNLOCK(&cache->gc_lock);
return 1;
}
|
