source: trunk/lib/lru_cache.c @ 292

Last change on this file since 292 was 286, checked in by tim, 9 years ago

Fixed a NULL pointer dereference and one dangling pointer, triggered by corrupt security descriptors.
Thanks AFL!

  • Property svn:keywords set to Id
File size: 7.9 KB
Line 
1/*
2 * Copyright (C) 2008-2009 Timothy D. Morgan
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 3 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
16 *
17 * $Id: lru_cache.c 286 2015-08-23 04:09:08Z tim $
18 */
19
20/**
21 * @file
22 */
23
24#include "lru_cache.h"
25
26
27#define LRU_CACHE_DEBUG 0
28
29/* XXX: really should replace this with a real universal hash or other
30 *      fast HMAC.
31 */ 
32static uint32_t lru_cache_compute_hash(uint32_t num_buckets,
33                                       uint32_t secret,
34                                       const void* buf,
35                                       uint32_t buf_len)
36{
37  uint32_t i;
38  uint32_t ret_val = 0x243f6a88;
39  unsigned char* s = (unsigned char*)&secret;
40  const unsigned char* b = (unsigned char*)buf;
41
42  for(i=0; i<buf_len; i++)
43    ret_val = (ret_val+(i^s[i%4])*b[i]) % num_buckets;
44 
45  return ret_val;
46}
47
48/* Returns approximately floor(log_2(n)) (log base 2 of n, floored)
49 * If n == 0, returns 0
50 */
51static uint32_t lru_cache_floor_log2(uint32_t n)
52{
53  uint32_t ret_val;
54 
55  for(ret_val=31; ret_val > 1; ret_val--)
56    if((n & (1 << ret_val)) != 0)
57      return ret_val;
58
59  return 0;
60}
61
62#if 0
63_EXPORT()
64void lru_cache_print(lru_cache* ht)
65{
66  uint32_t i;
67  lru_cache_element* cur;
68
69  printf("from newest to oldest:\n");
70  for(cur=ht->newest; cur != NULL; cur=cur->older)
71  {
72    /*    write(STDOUT_FILENO, cur->index, cur->index_len);*/
73    printf("%p", (void*)cur);
74    printf("\n");
75    if(cur->older == ht->newest)
76    {
77      printf("??? Loop in LRU list!!");
78      break;
79    }
80  }
81  printf("\n");
82
83  printf("table:\n");
84  for(i=0; i<ht->num_buckets; i++)
85  {
86    printf("%.8X: ", i);
87    for(cur=ht->table[i]; cur != NULL; cur=cur->next)
88    {
89      /*      write(STDOUT_FILENO, cur->index, cur->index_len);*/
90      printf("%p", (void*)cur);
91      printf("|");
92
93      if(cur->next == ht->table[i])
94      {
95        printf("??? Loop in table chain!!");
96        break;
97      }
98    }
99    printf("\n");
100  }
101}
102#endif
103
104
105lru_cache* lru_cache_create(uint32_t max_keys, uint32_t secret)
106{
107  return lru_cache_create_ctx(NULL, max_keys, secret, false);
108}
109
110
111lru_cache* lru_cache_create_ctx(void* talloc_ctx, uint32_t max_keys, 
112                                uint32_t secret, bool talloc_data)
113{
114  lru_cache* ret_val;
115
116  ret_val = talloc(talloc_ctx, lru_cache);
117  if(ret_val == NULL)
118    return NULL;
119
120  if(max_keys == 0)
121    ret_val->num_buckets = 1024;
122  else if(max_keys == 1)
123    ret_val->num_buckets = 1;   
124  else
125  {
126    ret_val->num_buckets = max_keys/lru_cache_floor_log2(max_keys);
127    if(ret_val->num_buckets < 1)
128      ret_val->num_buckets = 1;
129  }
130 
131  ret_val->table = talloc_array(ret_val, 
132                                lru_cache_element*, ret_val->num_buckets);
133  if(ret_val->table == NULL)
134  {
135    talloc_free(ret_val);
136    return NULL;
137  }
138 
139  ret_val->oldest = NULL;
140  ret_val->newest = NULL;
141  ret_val->max_keys = max_keys;
142  ret_val->secret = secret;
143  ret_val->talloc_data = talloc_data;
144  ret_val->num_keys = 0;
145  memset(ret_val->table, 0, ret_val->num_buckets*sizeof(lru_cache_element*));
146
147  return ret_val;
148}
149
150
151void lru_cache_destroy(lru_cache* ht)
152{
153  ht->secret = 0;
154  talloc_unlink(NULL, ht);
155}
156
157
158
159bool lru_cache_update(lru_cache* ht, const void* index, 
160                      uint32_t index_len, void* data)
161{
162  uint32_t hash, lru_hash;
163  lru_cache_element* cur;
164  lru_cache_element* last = NULL;
165  lru_cache_element* e = NULL;
166  void* tmp_index;
167
168  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
169  for(cur = ht->table[hash]; cur != NULL && e == NULL; cur=cur->next)
170  {
171    if((index_len == cur->index_len) 
172       && memcmp(cur->index, index, index_len) == 0)
173    { e = cur; }
174  }
175 
176  if(e != NULL)
177  { /* We found the index, so we're going to overwrite the data.
178     * We also need to reposition the element to the newest position,
179     * so remove it from the list for now.
180     */
181    if(ht->talloc_data)
182      talloc_unlink(e, e->data);
183
184    if(e->newer == NULL)
185      ht->newest = e->older;
186    else
187      e->newer->older = e->older;
188
189    if(e->older == NULL)
190      ht->oldest = e->newer;
191    else
192      e->older->newer = e->newer;
193  }
194  else
195  { /* We didn't find an identical index. */
196   
197    if((ht->max_keys != 0) && (ht->num_keys >= ht->max_keys))
198    { /* Eliminate the least recently used item, but reuse the element
199       * structure to minimize reallocation.
200       */
201      e = ht->oldest;
202      if(ht->newest == ht->oldest)
203      {
204        ht->newest = NULL;
205        ht->oldest = NULL;
206      }
207      else
208      {
209        ht->oldest = e->newer;
210        e->newer->older = NULL;
211      }
212      e->newer = NULL;
213      e->older = NULL;
214
215      last = NULL;
216      lru_hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, 
217                                        e->index, e->index_len);
218      for(cur = ht->table[lru_hash]; cur != e && cur != NULL; 
219          last=cur, cur=cur->next)
220      { continue; }
221
222      if(last == NULL)
223        ht->table[lru_hash] = e->next;
224      else
225        last->next = e->next;
226      e->next = NULL;
227
228      if(ht->talloc_data)
229        talloc_unlink(e, e->data);
230
231      tmp_index = talloc_realloc_size(e, e->index, index_len);
232      if(tmp_index == NULL)
233      {
234        talloc_free(e);
235        return false;
236      }
237      else
238        e->index = tmp_index;
239    }
240    else
241    { /* Brand new element because we have room to spare. */
242
243      e = talloc(ht->table, lru_cache_element);
244      if(e == NULL)
245        return false;
246     
247      e->index = talloc_size(e, index_len);
248      if(e->index == NULL)
249      {
250        talloc_free(e);
251        return false;
252      }
253     
254      /* New entry, increment counters. */
255      ht->num_keys++;
256    }
257    memcpy(e->index, index, index_len);
258    e->index_len = index_len;
259
260    e->next = ht->table[hash];
261    ht->table[hash] = e;
262  }
263  if(ht->talloc_data)
264    data = talloc_reference(e, data);
265  e->data = data;
266
267  /* Finally, let's insert the element to the newest position in the LRU list.*/
268  if(ht->newest != NULL)
269    ht->newest->newer = e;
270  e->newer = NULL;
271  e->older = ht->newest;
272  ht->newest = e;
273  if(ht->oldest == NULL)
274    ht->oldest = e;
275
276  return true;
277}
278
279
280void* lru_cache_find(lru_cache* ht, const void* index,
281                     uint32_t index_len)
282{
283  uint32_t hash;
284  lru_cache_element* cur;
285
286  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
287  for(cur = ht->table[hash]; (cur != NULL); cur = cur->next)
288  {
289    if((index_len == cur->index_len)
290       && memcmp(cur->index, index, index_len) == 0)
291    { break; }
292  }
293 
294  if(cur != NULL && cur->newer != NULL)
295  { /* Need to move this element up to the newest slot. */
296
297    cur->newer->older = cur->older;
298
299    if(cur->older == NULL)
300      ht->oldest = cur->newer;
301    else
302      cur->older->newer = cur->newer;
303
304    cur->newer = NULL;
305    cur->older = ht->newest;
306    ht->newest->newer = cur;
307    ht->newest = cur;
308  }
309
310  if(cur != NULL)
311    return cur->data;
312  else
313    return NULL;
314}
315
316
317
318bool lru_cache_remove(lru_cache* ht, const void* index, 
319                      uint32_t index_len)
320{
321  uint32_t hash;
322  lru_cache_element* cur;
323  lru_cache_element* last = NULL;
324
325  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret,
326                                index, index_len);
327  for(cur=ht->table[hash]; (cur != NULL);
328      last=cur, cur=cur->next)
329  {
330    if((index_len == cur->index_len) 
331       && memcmp(cur->index, index, index_len) == 0)
332    { break; }
333  }
334
335  if(cur == NULL)
336    return false;
337
338  /* Detach from list */
339  if(cur->newer == NULL)
340    ht->newest = cur->older;
341  else
342    cur->newer->older = cur->older;
343 
344  if(cur->older == NULL)
345    ht->oldest = cur->newer;
346  else
347    cur->older->newer = cur->newer;
348
349  /* Detach from hash table */
350  if(last == NULL)
351    ht->table[hash] = cur->next;
352  else
353    last->next = cur->next;
354
355  talloc_free(cur);
356 
357  /* Removing entry, decrement counters. */
358  ht->num_keys--;
359 
360  return true;
361}
Note: See TracBrowser for help on using the repository browser.