aboutsummaryrefslogtreecommitdiff
path: root/nscd/mem.c
diff options
context:
space:
mode:
Diffstat (limited to 'nscd/mem.c')
-rw-r--r--nscd/mem.c515
1 files changed, 515 insertions, 0 deletions
diff --git a/nscd/mem.c b/nscd/mem.c
new file mode 100644
index 0000000000..a4e30535c8
--- /dev/null
+++ b/nscd/mem.c
@@ -0,0 +1,515 @@
+/* Cache memory handling.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Contributed by Ulrich Drepper <drepper@redhat.com>, 2004.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
+#include <assert.h>
+#include <errno.h>
+#include <error.h>
+#include <inttypes.h>
+#include <libintl.h>
+#include <limits.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"
+
+
+/* Maximum alignment requirement we will encounter. */
+#define BLOCK_ALIGN_LOG 3
+#define BLOCK_ALIGN (1 << BLOCK_ALIGN_LOG)
+#define BLOCK_ALIGN_M1 (BLOCK_ALIGN - 1)
+
+
+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. */
+ 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++] |= 0xff << (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[(db->head->first_free / BLOCK_ALIGN + BITS - 1) / BITS];
+ memset (mark, '\0', sizeof (mark));
+
+ /* Create an array which can hold pointer to all the entries in hash
+ entries. */
+ struct hashentry *he[db->head->nentries];
+ struct hashentry *he_data[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);
+
+ /* Determine the highest used address. */
+ size_t high = sizeof (mark);
+ 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;
+ }
+
+ /* No 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;
+
+
+ /* 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
+ = (struct moveinfo *) alloca (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 (__builtin_expect (debug_level >= 3, 0))
+ dbg_log (_("freed %zu bytes in %s cache"),
+ 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 (__builtin_expect (debug_level >= 3, 0))
+ {
+ 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),
+ 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, he->len, 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),
+ 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, dh->allocsize,
+ 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);
+
+ /* We are done. */
+ out:
+ pthread_mutex_unlock (&db->memlock);
+ pthread_rwlock_unlock (&db->lock);
+}
+
+
+void *
+mempool_alloc (struct database_dyn *db, size_t len)
+{
+ /* 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);
+
+ 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 (__builtin_expect (db->head->first_free + len > db->head->data_size, 0))
+ {
+ if (! tried_resize)
+ {
+ /* Try to resize the database. Grow size of 1/8th. */
+ size_t new_data_size = db->head->data_size + db->head->data_size / 8;
+ size_t oldtotal = (sizeof (struct database_pers_head)
+ + db->head->module * sizeof (ref_t)
+ + db->head->data_size);
+ size_t newtotal = (sizeof (struct database_pers_head)
+ + db->head->module * sizeof (ref_t)
+ + new_data_size);
+
+ if ((!db->mmap_used || ftruncate (db->wr_fd, newtotal) != 0)
+ /* Try to resize the mapping. Note: no MREMAP_MAYMOVE. */
+ && mremap (db->head, oldtotal, newtotal, 0) == 0)
+ {
+ db->head->data_size = new_data_size;
+ tried_resize = true;
+ goto retry;
+ }
+ }
+
+ if (! db->last_alloc_failed)
+ {
+ dbg_log (_("no more memory for database '%s'"), dbnames[db - dbs]);
+
+ db->last_alloc_failed = true;
+ }
+
+ /* No luck. */
+ res = NULL;
+ }
+ else
+ {
+ db->head->first_free += len;
+
+ db->last_alloc_failed = false;
+ }
+
+ pthread_mutex_unlock (&db->memlock);
+
+ return res;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-11 11:38:44 +0000