/* Cache memory handling.
Copyright (C) 2004-2018 Free Software Foundation, Inc.
This file is part of the GNU C Library.
Contributed by Ulrich Drepper <drepper@redhat.com>, 2004.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
by the Free Software Foundation; version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, see <http://www.gnu.org/licenses/>. */
#include <assert.h>
#include <errno.h>
#include <error.h>
#include <fcntl.h>
#include <inttypes.h>
#include <libintl.h>
#include <limits.h>
#include <obstack.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/param.h>
#include "dbg_log.h"
#include "nscd.h"
static int
sort_he (const void *p1, const void *p2)
{
struct hashentry *h1 = *(struct hashentry **) p1;
struct hashentry *h2 = *(struct hashentry **) p2;
if (h1 < h2)
return -1;
if (h1 > h2)
return 1;
return 0;
}
static int
sort_he_data (const void *p1, const void *p2)
{
struct hashentry *h1 = *(struct hashentry **) p1;
struct hashentry *h2 = *(struct hashentry **) p2;
if (h1->packet < h2->packet)
return -1;
if (h1->packet > h2->packet)
return 1;
return 0;
}
/* Basic definitions for the bitmap implementation. Only BITMAP_T
needs to be changed to choose a different word size. */
#define BITMAP_T uint8_t
#define BITS (CHAR_BIT * sizeof (BITMAP_T))
#define ALLBITS ((((BITMAP_T) 1) << BITS) - 1)
#define HIGHBIT (((BITMAP_T) 1) << (BITS - 1))
static void
markrange (BITMAP_T *mark, ref_t start, size_t len)
{
/* Adjust parameters for block alignment. */
assert ((start & BLOCK_ALIGN_M1) == 0);
start /= BLOCK_ALIGN;
len = (len + BLOCK_ALIGN_M1) / BLOCK_ALIGN;
size_t elem = start / BITS;
if (start % BITS != 0)
{
if (start % BITS + len <= BITS)
{
/* All fits in the partial byte. */
mark[elem] |= (ALLBITS >> (BITS - len)) << (start % BITS);
return;
}
mark[elem++] |= ALLBITS << (start % BITS);
len -= BITS - (start % BITS);
}
while (len >= BITS)
{
mark[elem++] = ALLBITS;
len -= BITS;
}
if (len > 0)
mark[elem] |= ALLBITS >> (BITS - len);
}
void
gc (struct database_dyn *db)
{
/* We need write access. */
pthread_rwlock_wrlock (&db->lock);
/* And the memory handling lock. */
pthread_mutex_lock (&db->memlock);
/* We need an array representing the data area. All memory
allocation is BLOCK_ALIGN aligned so this is the level at which
we have to look at the memory. We use a mark and sweep algorithm
where the marks are placed in this array. */
assert (db->head->first_free % BLOCK_ALIGN == 0);
BITMAP_T *mark;
bool mark_use_malloc;
/* In prune_cache we are also using a dynamically allocated array.
If the array in the caller is too large we have malloc'ed it. */
size_t stack_used = sizeof (bool) * db->head->module;
if (__glibc_unlikely (stack_used > MAX_STACK_USE))
stack_used = 0;
size_t nmark = (db->head->first_free / BLOCK_ALIGN + BITS - 1) / BITS;
size_t memory_needed = nmark * sizeof (BITMAP_T);
if (__glibc_likely (stack_used + memory_needed <= MAX_STACK_USE))
{
mark = (BITMAP_T *) alloca_account (memory_needed, stack_used);
mark_use_malloc = false;
memset (mark, '\0', memory_needed);
}
else
{
mark = (BITMAP_T *) xcalloc (1, memory_needed);
mark_use_malloc = true;
}
/* Create an array which can hold pointer to all the entries in hash
entries. */
memory_needed = 2 * db->head->nentries * sizeof (struct hashentry *);
struct hashentry **he;
struct hashentry **he_data;
bool he_use_malloc;
if (__glibc_likely (stack_used + memory_needed <= MAX_STACK_USE))
{
he = alloca_account (memory_needed, stack_used);
he_use_malloc = false;
}
else
{
he = xmalloc (memory_needed);
he_use_malloc = true;
}
he_data = &he[db->head->nentries];
size_t cnt = 0;
for (size_t idx = 0; idx < db->head->module; ++idx)
{
ref_t *prevp = &db->head->array[idx];
ref_t run = *prevp;
while (run != ENDREF)
{
assert (cnt < db->head->nentries);
he[cnt] = (struct hashentry *) (db->data + run);
he[cnt]->prevp = prevp;
prevp = &he[cnt]->next;
/* This is the hash entry itself. */
markrange (mark, run, sizeof (struct hashentry));
/* Add the information for the data itself. We do this
only for the one special entry marked with FIRST. */
if (he[cnt]->first)
{
struct datahead *dh
= (struct datahead *) (db->data + he[cnt]->packet);
markrange (mark, he[cnt]->packet, dh->allocsize);
}
run = he[cnt]->next;
++cnt;
}
}
assert (cnt == db->head->nentries);
/* Sort the entries by the addresses of the referenced data. All
the entries pointing to the same DATAHEAD object will have the
same key. Stability of the sorting is unimportant. */
memcpy (he_data, he, cnt * sizeof (struct hashentry *));
qsort (he_data, cnt, sizeof (struct hashentry *), sort_he_data);
/* Sort the entries by their address. */
qsort (he, cnt, sizeof (struct hashentry *), sort_he);
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
struct obstack ob;
obstack_init (&ob);
/* Determine the highest used address. */
size_t high = nmark;
while (high > 0 && mark[high - 1] == 0)
--high;
/* No memory used. */
if (high == 0)
{
db->head->first_free = 0;
goto out;
}
/* Determine the highest offset. */
BITMAP_T mask = HIGHBIT;
ref_t highref = (high * BITS - 1) * BLOCK_ALIGN;
while ((mark[high - 1] & mask) == 0)
{
mask >>= 1;
highref -= BLOCK_ALIGN;
}
/* Now we can iterate over the MARK array and find bits which are not
set. These represent memory which can be recovered. */
size_t byte = 0;
/* Find the first gap. */
while (byte < high && mark[byte] == ALLBITS)
++byte;
if (byte == high
|| (byte == high - 1 && (mark[byte] & ~(mask | (mask - 1))) == 0))
/* No gap. */
goto out;
mask = 1;
cnt = 0;
while ((mark[byte] & mask) != 0)
{
++cnt;
mask <<= 1;
}
ref_t off_free = (byte * BITS + cnt) * BLOCK_ALIGN;
assert (off_free <= db->head->first_free);
struct hashentry **next_hash = he;
struct hashentry **next_data = he_data;
/* Skip over the hash entries in the first block which does not get
moved. */
while (next_hash < &he[db->head->nentries]
&& *next_hash < (struct hashentry *) (db->data + off_free))
++next_hash;
while (next_data < &he_data[db->head->nentries]
&& (*next_data)->packet < off_free)
++next_data;
/* Now we start modifying the data. Make sure all readers of the
data are aware of this and temporarily don't use the data. */
++db->head->gc_cycle;
assert ((db->head->gc_cycle & 1) == 1);
/* We do not perform the move operations right away since the
he_data array is not sorted by the address of the data. */
struct moveinfo
{
void *from;
void *to;
size_t size;
struct moveinfo *next;
} *moves = NULL;
while (byte < high)
{
/* Search for the next filled block. BYTE is the index of the
entry in MARK, MASK is the bit, and CNT is the bit number.
OFF_FILLED is the corresponding offset. */
if ((mark[byte] & ~(mask - 1)) == 0)
{
/* No other bit set in the same element of MARK. Search in the
following memory. */
do
++byte;
while (byte < high && mark[byte] == 0);
if (byte == high)
/* That was it. */
break;
mask = 1;
cnt = 0;
}
/* Find the exact bit. */
while ((mark[byte] & mask) == 0)
{
++cnt;
mask <<= 1;
}
ref_t off_alloc = (byte * BITS + cnt) * BLOCK_ALIGN;
assert (off_alloc <= db->head->first_free);
/* Find the end of the used area. */
if ((mark[byte] & ~(mask - 1)) == (BITMAP_T) ~(mask - 1))
{
/* All other bits set. Search the next bytes in MARK. */
do
++byte;
while (byte < high && mark[byte] == ALLBITS);
mask = 1;
cnt = 0;
}
if (byte < high)
{
/* Find the exact bit. */
while ((mark[byte] & mask) != 0)
{
++cnt;
mask <<= 1;
}
}
ref_t off_allocend = (byte * BITS + cnt) * BLOCK_ALIGN;
assert (off_allocend <= db->head->first_free);
/* Now we know that we can copy the area from OFF_ALLOC to
OFF_ALLOCEND (not included) to the memory starting at
OFF_FREE. First fix up all the entries for the
displacement. */
ref_t disp = off_alloc - off_free;
struct moveinfo *new_move;
if (__builtin_expect (stack_used + sizeof (*new_move) <= MAX_STACK_USE,
1))
new_move = alloca_account (sizeof (*new_move), stack_used);
else
new_move = obstack_alloc (&ob, sizeof (*new_move));
new_move->from = db->data + off_alloc;
new_move->to = db->data + off_free;
new_move->size = off_allocend - off_alloc;
/* Create a circular list to be always able to append at the end. */
if (moves == NULL)
moves = new_move->next = new_move;
else
{
new_move->next = moves->next;
moves = moves->next = new_move;
}
/* The following loop will prepare to move this much data. */
off_free += off_allocend - off_alloc;
while (off_alloc < off_allocend)
{
/* Determine whether the next entry is for a hash entry or
the data. */
if ((struct hashentry *) (db->data + off_alloc) == *next_hash)
{
/* Just correct the forward reference. */
*(*next_hash++)->prevp -= disp;
off_alloc += ((sizeof (struct hashentry) + BLOCK_ALIGN_M1)
& ~BLOCK_ALIGN_M1);
}
else
{
assert (next_data < &he_data[db->head->nentries]);
assert ((*next_data)->packet == off_alloc);
struct datahead *dh = (struct datahead *) (db->data + off_alloc);
do
{
assert ((*next_data)->key >= (*next_data)->packet);
assert ((*next_data)->key + (*next_data)->len
<= (*next_data)->packet + dh->allocsize);
(*next_data)->packet -= disp;
(*next_data)->key -= disp;
++next_data;
}
while (next_data < &he_data[db->head->nentries]
&& (*next_data)->packet == off_alloc);
off_alloc += (dh->allocsize + BLOCK_ALIGN_M1) & ~BLOCK_ALIGN_M1;
}
}
assert (off_alloc == off_allocend);
assert (off_alloc <= db->head->first_free);
if (off_alloc == db->head->first_free)
/* We are done, that was the last block. */
break;
}
assert (next_hash == &he[db->head->nentries]);
assert (next_data == &he_data[db->head->nentries]);
/* Now perform the actual moves. */
if (moves != NULL)
{
struct moveinfo *runp = moves->next;
do
{
assert ((char *) runp->to >= db->data);
assert ((char *) runp->to + runp->size
<= db->data + db->head->first_free);
assert ((char *) runp->from >= db->data);
assert ((char *) runp->from + runp->size
<= db->data + db->head->first_free);
/* The regions may overlap. */
memmove (runp->to, runp->from, runp->size);
runp = runp->next;
}
while (runp != moves->next);
if (__glibc_unlikely (debug_level >= 3))
dbg_log (_("freed %zu bytes in %s cache"),
(size_t) (db->head->first_free
- ((char *) moves->to + moves->size - db->data)),
dbnames[db - dbs]);
/* The byte past the end of the last copied block is the next
available byte. */
db->head->first_free = (char *) moves->to + moves->size - db->data;
/* Consistency check. */
if (__glibc_unlikely (debug_level >= 3))
{
for (size_t idx = 0; idx < db->head->module; ++idx)
{
ref_t run = db->head->array[idx];
size_t cnt = 0;
while (run != ENDREF)
{
if (run + sizeof (struct hashentry) > db->head->first_free)
{
dbg_log ("entry %zu in hash bucket %zu out of bounds: "
"%" PRIu32 "+%zu > %zu\n",
cnt, idx, run, sizeof (struct hashentry),
(size_t) db->head->first_free);
break;
}
struct hashentry *he = (struct hashentry *) (db->data + run);
if (he->key + he->len > db->head->first_free)
dbg_log ("key of entry %zu in hash bucket %zu out of "
"bounds: %" PRIu32 "+%zu > %zu\n",
cnt, idx, he->key, (size_t) he->len,
(size_t) db->head->first_free);
if (he->packet + sizeof (struct datahead)
> db->head->first_free)
dbg_log ("packet of entry %zu in hash bucket %zu out of "
"bounds: %" PRIu32 "+%zu > %zu\n",
cnt, idx, he->packet, sizeof (struct datahead),
(size_t) db->head->first_free);
else
{
struct datahead *dh = (struct datahead *) (db->data
+ he->packet);
if (he->packet + dh->allocsize
> db->head->first_free)
dbg_log ("full key of entry %zu in hash bucket %zu "
"out of bounds: %" PRIu32 "+%zu > %zu",
cnt, idx, he->packet, (size_t) dh->allocsize,
(size_t) db->head->first_free);
}
run = he->next;
++cnt;
}
}
}
}
/* Make sure the data on disk is updated. */
if (db->persistent)
msync (db->head, db->data + db->head->first_free - (char *) db->head,
MS_ASYNC);
/* Now we are done modifying the data. */
++db->head->gc_cycle;
assert ((db->head->gc_cycle & 1) == 0);
/* We are done. */
out:
pthread_mutex_unlock (&db->memlock);
pthread_rwlock_unlock (&db->lock);
if (he_use_malloc)
free (he);
if (mark_use_malloc)
free (mark);
obstack_free (&ob, NULL);
}
void *
mempool_alloc (struct database_dyn *db, size_t len, int data_alloc)
{
/* Make sure LEN is a multiple of our maximum alignment so we can
keep track of used memory is multiples of this alignment value. */
if ((len & BLOCK_ALIGN_M1) != 0)
len += BLOCK_ALIGN - (len & BLOCK_ALIGN_M1);
if (data_alloc)
pthread_rwlock_rdlock (&db->lock);
pthread_mutex_lock (&db->memlock);
assert ((db->head->first_free & BLOCK_ALIGN_M1) == 0);
bool tried_resize = false;
void *res;
retry:
res = db->data + db->head->first_free;
if (__glibc_unlikely (db->head->first_free + len > db->head->data_size))
{
if (! tried_resize)
{
/* Try to resize the database. Grow size of 1/8th. */
size_t oldtotal = (sizeof (struct database_pers_head)
+ roundup (db->head->module * sizeof (ref_t),
ALIGN)
+ db->head->data_size);
size_t new_data_size = (db->head->data_size
+ MAX (2 * len, db->head->data_size / 8));
size_t newtotal = (sizeof (struct database_pers_head)
+ roundup (db->head->module * sizeof (ref_t), ALIGN)
+ new_data_size);
if (newtotal > db->max_db_size)
{
new_data_size -= newtotal - db->max_db_size;
newtotal = db->max_db_size;
}
if (db->mmap_used && newtotal > oldtotal
/* We only have to adjust the file size. The new pages
become magically available. */
&& TEMP_FAILURE_RETRY_VAL (posix_fallocate (db->wr_fd, oldtotal,
newtotal
- oldtotal)) == 0)
{
db->head->data_size = new_data_size;
tried_resize = true;
goto retry;
}
}
if (data_alloc)
pthread_rwlock_unlock (&db->lock);
if (! db->last_alloc_failed)
{
dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
db->last_alloc_failed = true;
}
++db->head->addfailed;
/* No luck. */
res = NULL;
}
else
{
db->head->first_free += len;
db->last_alloc_failed = false;
}
pthread_mutex_unlock (&db->memlock);
return res;
}