1 /* Cache memory handling.
2 Copyright (C) 2004 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Ulrich Drepper <drepper@redhat.com>, 2004.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
31 #include <sys/param.h>
37 /* Maximum alignment requirement we will encounter. */
38 #define BLOCK_ALIGN_LOG 3
39 #define BLOCK_ALIGN (1 << BLOCK_ALIGN_LOG)
40 #define BLOCK_ALIGN_M1 (BLOCK_ALIGN - 1)
44 sort_he (const void *p1
, const void *p2
)
46 struct hashentry
*h1
= *(struct hashentry
**) p1
;
47 struct hashentry
*h2
= *(struct hashentry
**) p2
;
58 sort_he_data (const void *p1
, const void *p2
)
60 struct hashentry
*h1
= *(struct hashentry
**) p1
;
61 struct hashentry
*h2
= *(struct hashentry
**) p2
;
63 if (h1
->packet
< h2
->packet
)
65 if (h1
->packet
> h2
->packet
)
71 /* Basic definitions for the bitmap implementation. Only BITMAP_T
72 needs to be changed to choose a different word size. */
73 #define BITMAP_T uint8_t
74 #define BITS (CHAR_BIT * sizeof (BITMAP_T))
75 #define ALLBITS ((((BITMAP_T) 1) << BITS) - 1)
76 #define HIGHBIT (((BITMAP_T) 1) << (BITS - 1))
80 markrange (BITMAP_T
*mark
, ref_t start
, size_t len
)
82 /* Adjust parameters for block alignment. */
84 len
= (len
+ BLOCK_ALIGN_M1
) / BLOCK_ALIGN
;
86 size_t elem
= start
/ BITS
;
88 if (start
% BITS
!= 0)
90 if (start
% BITS
+ len
<= BITS
)
92 /* All fits in the partial byte. */
93 mark
[elem
] |= (ALLBITS
>> (BITS
- len
)) << (start
% BITS
);
97 mark
[elem
++] |= 0xff << (start
% BITS
);
98 len
-= BITS
- (start
% BITS
);
103 mark
[elem
++] = ALLBITS
;
108 mark
[elem
] |= ALLBITS
>> (BITS
- len
);
113 gc (struct database_dyn
*db
)
115 /* We need write access. */
116 pthread_rwlock_wrlock (&db
->lock
);
118 /* And the memory handling lock. */
119 pthread_mutex_lock (&db
->memlock
);
121 /* We need an array representing the data area. All memory
122 allocation is BLOCK_ALIGN aligned so this is the level at which
123 we have to look at the memory. We use a mark and sweep algorithm
124 where the marks are placed in this array. */
125 assert (db
->head
->first_free
% BLOCK_ALIGN
== 0);
126 BITMAP_T mark
[(db
->head
->first_free
/ BLOCK_ALIGN
+ BITS
- 1) / BITS
];
127 memset (mark
, '\0', sizeof (mark
));
129 /* Create an array which can hold pointer to all the entries in hash
131 struct hashentry
*he
[db
->head
->nentries
];
132 struct hashentry
*he_data
[db
->head
->nentries
];
135 for (size_t idx
= 0; idx
< db
->head
->module
; ++idx
)
137 ref_t
*prevp
= &db
->head
->array
[idx
];
140 while (run
!= ENDREF
)
142 assert (cnt
< db
->head
->nentries
);
143 he
[cnt
] = (struct hashentry
*) (db
->data
+ run
);
145 he
[cnt
]->prevp
= prevp
;
146 prevp
= &he
[cnt
]->next
;
148 /* This is the hash entry itself. */
149 markrange (mark
, run
, sizeof (struct hashentry
));
151 /* Add the information for the data itself. We do this
152 only for the one special entry marked with FIRST. */
156 = (struct datahead
*) (db
->data
+ he
[cnt
]->packet
);
157 markrange (mark
, he
[cnt
]->packet
, dh
->allocsize
);
165 assert (cnt
== db
->head
->nentries
);
167 /* Sort the entries by the addresses of the referenced data. All
168 the entries pointing to the same DATAHEAD object will have the
169 same key. Stability of the sorting is unimportant. */
170 memcpy (he_data
, he
, cnt
* sizeof (struct hashentry
*));
171 qsort (he_data
, cnt
, sizeof (struct hashentry
*), sort_he_data
);
173 /* Sort the entries by their address. */
174 qsort (he
, cnt
, sizeof (struct hashentry
*), sort_he
);
176 /* Determine the highest used address. */
177 size_t high
= sizeof (mark
);
178 while (high
> 0 && mark
[high
- 1] == 0)
181 /* No memory used. */
184 db
->head
->first_free
= 0;
188 /* Determine the highest offset. */
189 BITMAP_T mask
= HIGHBIT
;
190 ref_t highref
= (high
* BITS
- 1) * BLOCK_ALIGN
;
191 while ((mark
[high
- 1] & mask
) == 0)
194 highref
-= BLOCK_ALIGN
;
197 /* No we can iterate over the MARK array and find bits which are not
198 set. These represent memory which can be recovered. */
200 /* Find the first gap. */
201 while (byte
< high
&& mark
[byte
] == ALLBITS
)
205 || (byte
== high
- 1 && (mark
[byte
] & ~(mask
| (mask
- 1))) == 0))
211 while ((mark
[byte
] & mask
) != 0)
216 ref_t off_free
= (byte
* BITS
+ cnt
) * BLOCK_ALIGN
;
217 assert (off_free
<= db
->head
->first_free
);
219 struct hashentry
**next_hash
= he
;
220 struct hashentry
**next_data
= he_data
;
222 /* Skip over the hash entries in the first block which does not get
224 while (next_hash
< &he
[db
->head
->nentries
]
225 && *next_hash
< (struct hashentry
*) (db
->data
+ off_free
))
228 while (next_data
< &he_data
[db
->head
->nentries
]
229 && (*next_data
)->packet
< off_free
)
233 /* We do not perform the move operations right away since the
234 he_data array is not sorted by the address of the data. */
240 struct moveinfo
*next
;
245 /* Search for the next filled block. BYTE is the index of the
246 entry in MARK, MASK is the bit, and CNT is the bit number.
247 OFF_FILLED is the corresponding offset. */
248 if ((mark
[byte
] & ~(mask
- 1)) == 0)
250 /* No other bit set in the same element of MARK. Search in the
254 while (byte
< high
&& mark
[byte
] == 0);
263 /* Find the exact bit. */
264 while ((mark
[byte
] & mask
) == 0)
270 ref_t off_alloc
= (byte
* BITS
+ cnt
) * BLOCK_ALIGN
;
271 assert (off_alloc
<= db
->head
->first_free
);
273 /* Find the end of the used area. */
274 if ((mark
[byte
] & ~(mask
- 1)) == (BITMAP_T
) ~(mask
- 1))
276 /* All other bits set. Search the next bytes in MARK. */
279 while (byte
< high
&& mark
[byte
] == ALLBITS
);
286 /* Find the exact bit. */
287 while ((mark
[byte
] & mask
) != 0)
294 ref_t off_allocend
= (byte
* BITS
+ cnt
) * BLOCK_ALIGN
;
295 assert (off_allocend
<= db
->head
->first_free
);
296 /* Now we know that we can copy the area from OFF_ALLOC to
297 OFF_ALLOCEND (not included) to the memory starting at
298 OFF_FREE. First fix up all the entries for the
300 ref_t disp
= off_alloc
- off_free
;
302 struct moveinfo
*new_move
303 = (struct moveinfo
*) alloca (sizeof (*new_move
));
304 new_move
->from
= db
->data
+ off_alloc
;
305 new_move
->to
= db
->data
+ off_free
;
306 new_move
->size
= off_allocend
- off_alloc
;
307 /* Create a circular list to be always able to append at the end. */
309 moves
= new_move
->next
= new_move
;
312 new_move
->next
= moves
->next
;
313 moves
= moves
->next
= new_move
;
316 /* The following loop will prepare to move this much data. */
317 off_free
+= off_allocend
- off_alloc
;
319 while (off_alloc
< off_allocend
)
321 /* Determine whether the next entry is for a hash entry or
323 if ((struct hashentry
*) (db
->data
+ off_alloc
) == *next_hash
)
325 /* Just correct the forward reference. */
326 *(*next_hash
++)->prevp
-= disp
;
328 off_alloc
+= ((sizeof (struct hashentry
) + BLOCK_ALIGN_M1
)
333 assert (next_data
< &he_data
[db
->head
->nentries
]);
334 assert ((*next_data
)->packet
== off_alloc
);
336 struct datahead
*dh
= (struct datahead
*) (db
->data
+ off_alloc
);
339 assert ((*next_data
)->key
>= (*next_data
)->packet
);
340 assert ((*next_data
)->key
+ (*next_data
)->len
341 <= (*next_data
)->packet
+ dh
->allocsize
);
343 (*next_data
)->packet
-= disp
;
344 (*next_data
)->key
-= disp
;
347 while (next_data
< &he_data
[db
->head
->nentries
]
348 && (*next_data
)->packet
== off_alloc
);
350 off_alloc
+= (dh
->allocsize
+ BLOCK_ALIGN_M1
) & ~BLOCK_ALIGN_M1
;
353 assert (off_alloc
== off_allocend
);
355 assert (off_alloc
<= db
->head
->first_free
);
356 if (off_alloc
== db
->head
->first_free
)
357 /* We are done, that was the last block. */
360 assert (next_hash
== &he
[db
->head
->nentries
]);
361 assert (next_data
== &he_data
[db
->head
->nentries
]);
363 /* Now perform the actual moves. */
366 struct moveinfo
*runp
= moves
->next
;
369 assert ((char *) runp
->to
>= db
->data
);
370 assert ((char *) runp
->to
+ runp
->size
371 <= db
->data
+ db
->head
->first_free
);
372 assert ((char *) runp
->from
>= db
->data
);
373 assert ((char *) runp
->from
+ runp
->size
374 <= db
->data
+ db
->head
->first_free
);
376 /* The regions may overlap. */
377 memmove (runp
->to
, runp
->from
, runp
->size
);
380 while (runp
!= moves
->next
);
382 if (__builtin_expect (debug_level
>= 3, 0))
383 dbg_log (_("freed %zu bytes in %s cache"),
385 - ((char *) moves
->to
+ moves
->size
- db
->data
),
388 /* The byte past the end of the last copied block is the next
390 db
->head
->first_free
= (char *) moves
->to
+ moves
->size
- db
->data
;
392 /* Consistency check. */
393 if (__builtin_expect (debug_level
>= 3, 0))
395 for (size_t idx
= 0; idx
< db
->head
->module
; ++idx
)
397 ref_t run
= db
->head
->array
[idx
];
400 while (run
!= ENDREF
)
402 if (run
+ sizeof (struct hashentry
) > db
->head
->first_free
)
404 dbg_log ("entry %zu in hash bucket %zu out of bounds: "
405 "%" PRIu32
"+%zu > %zu\n",
406 cnt
, idx
, run
, sizeof (struct hashentry
),
407 db
->head
->first_free
);
411 struct hashentry
*he
= (struct hashentry
*) (db
->data
+ run
);
413 if (he
->key
+ he
->len
> db
->head
->first_free
)
414 dbg_log ("key of entry %zu in hash bucket %zu out of "
415 "bounds: %" PRIu32
"+%zu > %zu\n",
416 cnt
, idx
, he
->key
, he
->len
, db
->head
->first_free
);
418 if (he
->packet
+ sizeof (struct datahead
)
419 > db
->head
->first_free
)
420 dbg_log ("packet of entry %zu in hash bucket %zu out of "
421 "bounds: %" PRIu32
"+%zu > %zu\n",
422 cnt
, idx
, he
->packet
, sizeof (struct datahead
),
423 db
->head
->first_free
);
426 struct datahead
*dh
= (struct datahead
*) (db
->data
428 if (he
->packet
+ dh
->allocsize
429 > db
->head
->first_free
)
430 dbg_log ("full key of entry %zu in hash bucket %zu "
431 "out of bounds: %" PRIu32
"+%zu > %zu",
432 cnt
, idx
, he
->packet
, dh
->allocsize
,
433 db
->head
->first_free
);
443 /* Make sure the data on disk is updated. */
445 msync (db
->head
, db
->data
+ db
->head
->first_free
- (char *) db
->head
,
450 pthread_mutex_unlock (&db
->memlock
);
451 pthread_rwlock_unlock (&db
->lock
);
456 mempool_alloc (struct database_dyn
*db
, size_t len
)
458 /* Make sure LEN is a multiple of our maximum alignment so we can
459 keep track of used memory is multiples of this alignment value. */
460 if ((len
& BLOCK_ALIGN_M1
) != 0)
461 len
+= BLOCK_ALIGN
- (len
& BLOCK_ALIGN_M1
);
463 pthread_mutex_lock (&db
->memlock
);
465 assert ((db
->head
->first_free
& BLOCK_ALIGN_M1
) == 0);
467 bool tried_resize
= false;
470 res
= db
->data
+ db
->head
->first_free
;
472 if (__builtin_expect (db
->head
->first_free
+ len
> db
->head
->data_size
, 0))
476 /* Try to resize the database. Grow size of 1/8th. */
477 size_t new_data_size
= db
->head
->data_size
+ db
->head
->data_size
/ 8;
478 size_t oldtotal
= (sizeof (struct database_pers_head
)
479 + db
->head
->module
* sizeof (ref_t
)
480 + db
->head
->data_size
);
481 size_t newtotal
= (sizeof (struct database_pers_head
)
482 + db
->head
->module
* sizeof (ref_t
)
485 if ((!db
->mmap_used
|| ftruncate (db
->wr_fd
, newtotal
) != 0)
486 /* Try to resize the mapping. Note: no MREMAP_MAYMOVE. */
487 && mremap (db
->head
, oldtotal
, newtotal
, 0) == 0)
489 db
->head
->data_size
= new_data_size
;
495 if (! db
->last_alloc_failed
)
497 dbg_log (_("no more memory for database '%s'"), dbnames
[db
- dbs
]);
499 db
->last_alloc_failed
= true;
507 db
->head
->first_free
+= len
;
509 db
->last_alloc_failed
= false;
512 pthread_mutex_unlock (&db
->memlock
);