| /* 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; |
| } |